Comment résumer le plan

Nicolas Bonichon 1, 2 Cyril Gavoille 1, 2, * Nicolas Hanusse 1, 2 David Ilcinkas 1, 2 Ljubomir Perkovic 3
* Auteur correspondant
2 CEPAGE - Algorithmics for computationally intensive applications over wide scale distributed platforms
Université Sciences et Technologies - Bordeaux 1, Inria Bordeaux - Sud-Ouest, École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), CNRS - Centre National de la Recherche Scientifique : UMR5800
Résumé : Cet article concerne les graphes de recouvrement d'un ensemble fini de points du plan Euclidien. Un graphe de recouvrement $H$ est de facteur d'étirement $t$ pour un ensemble de points $S$ si, entre deux points quelconques de $S$, le coût d'un plus court chemin dans $H$ est au plus $t$ fois leur distance Euclidenne. Les graphes de recouvrement d'étirement $t$ (ci-après nommés \emph{$t$-spanneurs}) sont à la base de nombreux algorithmes de routage et de navigation dans le plan. Le graphe (ou triangulation) de Delaunay, le graphe de Gabriel, le graphe de Yao ou le Theta-graphe sont des exemples bien connus de $t$-spanneurs. L'étirement $t$ et le degré maximum des spanneurs sont des paramètres important à minimiser pour l'optimisation des ressources. En même temps le caractère planaire des constructions se révèle essentiel dans les algorithmes de navigation. Nous présentons une série de résultats dans ce domaine, en particulier: \begin{itemize} \item Nous montrons que le graphe $\Theta_6$ (le Theta-graphe où $k=6$ cônes d'angle $\Theta_k = 2\pi/k$ par sommet sont utilisées) est l'union de deux spanneurs planaires d'étirement deux. En particulier, nous établissons que l'étirement maximum du graphe $\Theta_6$ est deux, ce qui est optimal. Des bornes supérieures sur l'étirement du graphe $\Theta_k$ n'étaient connues que lorsque $k > 6$. Pour $k=7$, la meilleure borne connue est d'environ $7.56$ et pour $k=6$ il était ouvert de savoir si le graphe était un $t$-spanneur pour une valeur constante de $t$. \item Nous montrons que le graphe $\Theta_6$ contient comme sous-graphe couvrant un $3$-spanneur planaire de degré maximum au plus~$9$. \item Finalement, en utilisant une variante du résultat précédant, nous montrons que le plan Euclidien possède un $6$-spanneur planaire de degré maximum au plus~$6$. \end{itemize} La dernière construction, non décrite ici par manque de place, améliore une longue série de résultats sur le problème largement ouvert de déterminer la plus petite valeur $\delta$ telle que tout ensemble du plan possède un spanneur planaire d'étirement constant et de degré maximum $\delta$. Le meilleur résultat en date montrait que $3 \le \delta\le 14$.
Type de document :
Communication dans un congrès
Maria Gradinariu Potop-Butucaru et Hervé Rivano. 12èmes Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel), 2010, Belle Dune, France. 2010
Liste complète des métadonnées

Littérature citée [10 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00476151
Contributeur : Cyril Gavoille <>
Soumis le : vendredi 23 avril 2010 - 18:02:45
Dernière modification le : lundi 8 octobre 2018 - 20:42:06
Document(s) archivé(s) le : lundi 22 octobre 2012 - 15:22:49

Fichier

algotel.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00476151, version 1

Collections

Citation

Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse, David Ilcinkas, Ljubomir Perkovic. Comment résumer le plan. Maria Gradinariu Potop-Butucaru et Hervé Rivano. 12èmes Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel), 2010, Belle Dune, France. 2010. 〈inria-00476151〉

Partager

Métriques

Consultations de la notice

373

Téléchargements de fichiers

175