Routage compact optimal dans les $(k,r)$-constellations
Résumé
\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.