Longueur Arborescente des Graphes Série-Parallèles

Description

La longueur d'une décomposition arborescente d'un graphe G est la plus grande distance entre deux sommets d'un sac de la décomposition. La longueur arborescente de G est la plus petite longueur d'une de ses décompositions arborescentes. Ce paramètre aétéétudié pour ses applications algorithmiques dans des problèmes classiques comme le problème du voyageur de commerce ou le calcul de tables de routage compactes etégalement pour ses liens avec la largeur arborescente. Décider si la longueur arborescente d'un graphe quelconque est au plus 2 est NP-complet, et le meilleur algorithme d'approximation connu a un rapport d'approximation de 3 (il n'existe pas de c-approximation pour c < 3 2). Le problème de calculer la longueur arborescente est facile dans certaines classes de graphes comme celle des graphes planaires extérieurs. Cependant, rien n'est connu sur la complexité de ce problème dans d'autres classes de graphes planaires. Dans cet article, nousétudions ce problème dans la classe des graphes série-parallèles (graphes SP). Nous montrons que le problème est non-trivial dans les graphes melons, une sous-classe très simple des graphes SP. Nous concevons une 3 2-approximation pour calculer la longueur arborescente (et une décomposition correspondante) dans les graphes SP. Notre résultat principal est que décider si la longueur arborescente d'un graphe SP est au plus 2 peutêtre résolu en temps polynomial. Ce résultat se base sur une caractérisation de ces graphes par des sous-graphes isométriques interdits.

Abstract

National audience

Additional details