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

DIENG, Youssou; GAVOILLE, Cyril

doi:10.3166/TSI.30.485-513

Metadatos

Mostrar el registro completo del ítem

Licencia de uso del documento

DIENG, Youssou
Laboratoire Bordelais de Recherche en Informatique [LaBRI]

GAVOILLE, Cyril
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Institut universitaire de France [IUF]

Idioma

Article de revue

Este ítem está publicado en

Revue des Sciences et Technologies de l'Information - Série TSI : Technique et Science Informatiques. 2011-05, vol. 30, n° 05/2011, p. 485-513

Lavoisier

Resumen en inglés

\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.< Leer menos

Palabras clave en inglés

compact routing

free-minor graph

planar graph

outerplanar graph

Metadatos

Compartir este ítem

Licencia de uso del documento