Catalan structures and dynamic programming in H-minor-free graphs

Frederic Dorn 1 Fedor Fomin 1 Dimitrios M. Thilikos 2, 3
3 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : We give an algorithm that, for a fixed graph H and integer k, decides whether an n-vertex H-minor-free graph G contains a path of length k in $2^(O(\sqrt{k})) n^{O(1)}$ steps. Our approach builds on a combination of Demaine-Hajiaghayiʼs bounds on the size of an excluded grid in such graphs with a novel combinatorial result on certain branch decompositions of H-minor-free graphs. This result is used to bound the number of ways vertex disjoint paths can be routed through the separators of such decompositions. The proof is based on several structural theorems from the Graph Minors series of Robertson and Seymour. With a slight modification, similar combinatorial and algorithmic results can be derived for many other problems. Our approach can be viewed as a general framework for obtaining time $2^(O(\sqrt{k})) n^{O(1)}$ algorithms on H-minor-free graph classes.
Type de document :
Article dans une revue
Journal of Computer and System Sciences, Elsevier, 2012, 78 (5), pp.1606-1622. 〈http://www.sciencedirect.com/science/article/pii/S0022000012000505〉. 〈10.1016/j.jcss.2012.02.004〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00904498
Contributeur : Dimitrios M. Thilikos <>
Soumis le : jeudi 14 novembre 2013 - 15:43:35
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13

Identifiants

Collections

Citation

Frederic Dorn, Fedor Fomin, Dimitrios M. Thilikos. Catalan structures and dynamic programming in H-minor-free graphs. Journal of Computer and System Sciences, Elsevier, 2012, 78 (5), pp.1606-1622. 〈http://www.sciencedirect.com/science/article/pii/S0022000012000505〉. 〈10.1016/j.jcss.2012.02.004〉. 〈lirmm-00904498〉

Partager

Métriques

Consultations de la notice

78