ACCUEIL

Consignes aux
auteurs et coordonnateurs
Nos règles d'éthique
Auteurs : soumettez
votre article en ligne
Autres revues >>

Technique et Science Informatiques

0752-4072
Revue des sciences et technologies de l'information
 

 ARTICLE VOL 30/5 - 2011  - pp.485-513  - doi:10.3166/tsi.30.485-513
TITRE
Routage compact optimal dans les (k, r)-constellations

RÉSUMÉ

Fraigniaud et al., (2001) et indépendamment Thorup et al., (2001) ont montré que tout arbre à n noeuds possède un schéma de routage de plus courts chemins utilisant des adresses, des en-têtes et des tables de routage de O(log n) bits. Il est ouvert de savoir si ce résultat optimal peut être étendu, ne serait-ce qu’aux réseaux de largeur arborescente deux dont la meilleure borne connue, due à (Peleg, 2000) est O(log2 n) bits. Dans cet article, nous étendons ce résultat optimal aux réseaux appelés (k, r)-constellations, c’est-à-dire aux réseaux ne contenant pas K2,r comme mineur et dont les composantes bi-connexes peuvent être rendues planaire-extérieures par la suppression de k sommets. Par exemple, les (2, 4)- constellations contiennent les arbres, les graphes planaire-extérieurs et plus généralement les graphes sans mineur K2,4.



ABSTRACT
Fraigniaud et al., (2001) and independently Thorup et al., (2001) 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(log2 n) bits (cf. (Peleg, 2000)). In this article, we extend this optimal result to (k, r)-constellations, i.e., K2,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 K2,4-minor free networks.


AUTEUR(S)
Youssou DIENG, Cyril GAVOILLE

Reçu le 15 juin 2009.   

MOTS-CLÉS
routage compact, graphe sans mineur, graphe planaire, graphe planaire extérieur.

KEYWORDS
compact routing, free-minor graph, planar graph, outerplanar graph.

LANGUE DE L'ARTICLE
Français

 PRIX
• Abonné (hors accès direct) : 12.5 €
• Non abonné : 25.0 €
|
|
--> Tous les articles sont dans un format PDF protégé par tatouage 
   
ACCÉDER A L'ARTICLE COMPLET  (434 Ko)



Mot de passe oublié ?

ABONNEZ-VOUS !

CONTACTS
Comité de
rédaction
Conditions
générales de vente

 English version >> 
Lavoisier