Longueur linéaire des graphes planaires extérieurs

Autor: Dissaux, Thomas, Nisse, Nicolas
Přispěvatelé: Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), ANR-17-EURE-0004,UCA DS4H,UCA Systèmes Numériques pour l'Homme(2017), ANR-15-IDEX-0001,UCA JEDI,Idex UCA JEDI(2015)
Jazyk: francouzština
Rok vydání: 2022
Předmět:
Zdroj: AlgoTel 2022-24èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications
AlgoTel 2022-24èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, May 2022, Saint-Rémy-Lès-Chevreuse, France
Popis: International audience; 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.
Databáze: OpenAIRE
Externí odkaz: