Skip to Main content Skip to Navigation
Conference papers

Spanners additifs de taille sous-quadratique pour les graphes orientés

Résumé : Soit G un graphe général orienté valué avec n sommets. On définit une métrique d entre tous sommets u,v . Un sous-graphe couvrant H de G est dit un spanneur de G si pour tous u , v de G , on a : d_H(u,v) ≤ α*d_G(u,v)+β (α,β) étant nommé l'étirement, le but étant de faire le plus petit étirement possible avec le moins d'arêtes possible. Il est connu [Cowen99] que pour les graphes orientés valués, si l'on choisit d(u,v) comme la longueur d'un plus court chemin entre u et v, on ne peut pas avoir à la fois étirement borné et moins que n^2 arête dans le cas général. Dans [RTZ08], les auteurs introduisent la notion de métrique aller-retour, notée d*(u,v) telle qu'elle soit la somme des longueurs des plus courts chemins u→v et v→u . Les auteurs montrent que cette métrique est bien une distance et qu'elle fournit une définition utilisable de spanneur (nommés spanneurs aller/retour). Notamment, ils obtiennent un (2k+e,0)-spanneur avec O ((k^2/e) n^(1+1/k) log( nW )) arêtes, et explicitent un résultat plus ancien de (2^k−1,0) -spanneur avec O(n^(1+1/k) arêtes, pour tout k ≥ 1 et tout e>0 . Dans cet exposé il sera montré qu'il est possible de faire un étirement de (2 ,8W) avec O(n^(3/2)) arêtes. L'algorithme présenté repose sur une application d'un algorithme de sélection de nœuds glouton et d'applications successives de constructions d'arbres de plus court chemin. L'analyse du nombre d'arête se fait en extrayant un sous graphe de grande maille et l'étirement en appliquant le principe des inégalités triangulaires.
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-00984933
Contributor : Cyril Gavoille <>
Submitted on : Tuesday, April 29, 2014 - 9:51:58 AM
Last modification on : Wednesday, June 24, 2020 - 4:18:59 PM

Identifiers

  • HAL Id : hal-00984933, version 1

Citation

Cyril Gavoille, Quentin Godfroy, Laurent Viennot. Spanners additifs de taille sous-quadratique pour les graphes orientés. 12e Journées Graphes et Algorithmes, Oct 2010, Marseille, France. pp.9. ⟨hal-00984933⟩

Share

Metrics

Record views

546