Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Conference papers

Longueur linéaire des graphes planaires extérieurs

Thomas Dissaux 1 Nicolas Nisse 1 
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Résumé : Une décomposition linéaire (path-decomposition) d'un graphe G = (V, E) est une représentation de G comme une séquence de sous-ensembles (appelés sacs) de V vérifiant des propriétés de connexité. La longueur d'une décomposition linéaire est le plus grand diamètre d'un de ses sacs et la longueur linéaire de G est la plus petite longueur d'une de ses décompositions linéaires. Ce paramètre a été étudié pour ses applications algorithmiques dans des problèmes métriques classiques (e.g., plus court chemin d'excentricité minimum, plongement de graphes dans des espaces métriques avec faible distorsion des distances...). Il est connu que décider si la longueur linéaire d'un graphe quelconque est au plus 2 est NP-complet, et le meilleur algorithme d'approximation connu a un rapport d'approximation de 2 (il n'existe pas de c-approximation pour c < 3/2). Dans cet article, nous étudions ce problème dans des sous-classes des graphes planaires. Nous prouvons que la longueur linéaire d'un cycle de n sommets est n/2 et que celle des arbres peut être déterminée en temps linéaire. Notre résultat principal est un algorithme polynomial donnant une +1-approximation de la longueur linéaire des graphes planaires extérieurs 2-connexes. Cet algorithme repose sur le fait que, dans cette classe de graphes, nous prouvons qu'il existe des décompositions (presque) optimales (de longueur minimum à un près) avec des propriétés structurelles spécifiques.
Document type :
Conference papers
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-03655647
Contributor : Thomas Dissaux Connect in order to contact the contributor
Submitted on : Friday, April 29, 2022 - 5:59:58 PM
Last modification on : Tuesday, May 3, 2022 - 3:46:45 AM

File

Pathlength_Outerplanar.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03655647, version 1

Citation

Thomas Dissaux, Nicolas Nisse. Longueur linéaire des graphes planaires extérieurs. AlgoTel 2022 - 24èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, May 2022, Saint-Rémy-Lès-Chevreuse, France. ⟨hal-03655647⟩

Share

Metrics

Record views

6

Files downloads

6