Dynamic Programming for H-minor-free Graphs

Abstract : We provide a framework for the design and analysis of dynamic programming algorithms for H-minor-free graphs with branchwidth at most k. Our technique applies to a wide family of problems where standard (deterministic) dynamic programming runs in 2 O(k*logk)*n O(1) steps, with n being the number of vertices of the input graph. Extending the approach developed by the same authors for graphs embedded in surfaces, we introduce a new type of branch decomposition for H-minor-free graphs, called an H-minor-free cut decomposition, and we show that they can be constructed in O h (n 3) steps, where the hidden constant depends exclusively on H. We show that the separators of such decompositions have connected packings whose behavior can be described in terms of a combinatorial object called ℓ-triangulation. Our main result is that when applied on H-minor-free cut decompositions, dynamic programming runs in 2Oh(k)⋅nO(1) steps. This broadens substantially the class of problems that can be solved deterministically in single-exponential time for H-minor-free graphs.
Type de document :
Communication dans un congrès
Gudmundsson, Joachim and Mestre, Julien and Viglas, Taso. COCOON'12: 18th Annual International Computing and Combinatorics Conference, Australia. Springer Berlin Heidelberg, 7434, pp.86-97, 2012, 〈10.1007/978-3-642-32241-9_8〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00736708
Contributeur : Ignasi Sau <>
Soumis le : vendredi 28 septembre 2012 - 18:20:47
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Lien texte intégral

Identifiants

Collections

Citation

Juanjo Rué, Ignasi Sau, Dimitrios M. Thilikos. Dynamic Programming for H-minor-free Graphs. Gudmundsson, Joachim and Mestre, Julien and Viglas, Taso. COCOON'12: 18th Annual International Computing and Combinatorics Conference, Australia. Springer Berlin Heidelberg, 7434, pp.86-97, 2012, 〈10.1007/978-3-642-32241-9_8〉. 〈lirmm-00736708〉

Partager

Métriques

Consultations de la notice

149