Routage compact optimal dans les $(k,r)$-constellations
| Autor: | Youssou Dieng, Cyril Gavoille |
|---|---|
| Přispěvatelé: | Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Institut Universitaire de France (IUF), Ministère de l'Education nationale, de l’Enseignement supérieur et de la Recherche (M.E.N.E.S.R.), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest |
| Jazyk: | francouzština |
| Rok vydání: | 2011 |
| Předmět: |
compact routing
Node (networking) Routing table 010102 general mathematics [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] planar graph 0102 computer and information sciences free-minor graph Binary logarithm 01 natural sciences Combinatorics outerplanar graph 010201 computation theory & mathematics Scheme (mathematics) 0101 mathematics Routing (electronic design automation) Mathematics MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | Revue des Sciences et Technologies de l'Information-Série TSI : Technique et Science Informatiques Revue des Sciences et Technologies de l'Information-Série TSI : Technique et Science Informatiques, Lavoisier, 2011, 30 (05/2011), pp.485-513. ⟨10.3166/TSI.30.485-513⟩ Revue des Sciences et Technologies de l'Information-Série TSI : Technique et Science Informatiques, 2011, 30 (05/2011), pp.485-513. ⟨10.3166/TSI.30.485-513⟩ |
| ISSN: | 0752-4072 2116-5920 |
| DOI: | 10.3166/TSI.30.485-513⟩ |
| Popis: | International audience; \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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|