Mostrar el registro sencillo del ítem

Routage compact optimal dans les $(k,r)$-constellations

hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
dc.contributor.authorDIENG, Youssou
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
hal.structure.identifierInstitut universitaire de France [IUF]
dc.contributor.authorGAVOILLE, Cyril
dc.date.accessioned2024-04-15T09:46:18Z
dc.date.available2024-04-15T09:46:18Z
dc.date.issued2011-05
dc.identifier.issn0752-4072
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/197992
dc.description.abstractEn\cite{FG01a} and independently \cite{TZ01} show that $n$-node trees support routing schemes with message headers, node addresses, and routing tables of $O(\log n)$ bits. It still open to known if this optimal result can be extended to the tree-width two graphs. The best known routing scheme require $O(\log^2n)$ bits (cf.~\cite{Peleg00a}). In this article, we extend this optimal result to \emph{$(k,r)$-constellations}, i.e., $K_{2,r}$-minor free networks whose bi-connected components are outerplanar by deleting $k$ vertices. For example, $(2,4)$-constellations contain trees, outerplanars and more generally all $K_{2,4}$-minor free networks.
dc.language.isofr
dc.publisherLavoisier
dc.subject.encompact routing
dc.subject.enfree-minor graph
dc.subject.enplanar graph
dc.subject.enouterplanar graph
dc.titleRoutage compact optimal dans les $(k,r)$-constellations
dc.typeArticle de revue
dc.identifier.doi10.3166/TSI.30.485-513
dc.subject.halInformatique [cs]/Algorithme et structure de données [cs.DS]
bordeaux.journalRevue des Sciences et Technologies de l'Information - Série TSI : Technique et Science Informatiques
bordeaux.page485-513
bordeaux.volume30
bordeaux.hal.laboratoriesLaboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800*
bordeaux.issue05/2011
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.peerReviewedoui
hal.identifierhal-00651841
hal.version1
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-00651841v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.title=Routage%20compact%20optimal%20dans%20les%20$(k,r)$-constellations&rft.atitle=Routage%20compact%20optimal%20dans%20les%20$(k,r)$-constellations&rft.jtitle=Revue%20des%20Sciences%20et%20Technologies%20de%20l'Information%20-%20S%C3%A9rie%20TSI%20:%20Technique%20et%20Science%20Informatiques&rft.date=2011-05&rft.volume=30&rft.issue=05/2011&rft.spage=485-513&rft.epage=485-513&rft.eissn=0752-4072&rft.issn=0752-4072&rft.au=DIENG,%20Youssou&GAVOILLE,%20Cyril&rft.genre=article


Archivos en el ítem

ArchivosTamañoFormatoVer

No hay archivos asociados a este ítem.

Este ítem aparece en la(s) siguiente(s) colección(ones)

Mostrar el registro sencillo del ítem