Dynamic programming for graphs on surfaces

Abstract : We provide a framework for the design and analysis of dynamic programming algorithms for surface-embedded graphs on n vertices and branchwidth at most k. Our technique applies to general families of problems where standard dynamic programming runs in 2O(kċlog k)ċ n steps. Our approach combines tools from topological graph theory and analytic combinatorics. In particular, we introduce a new type of branch decomposition called surface cut decomposition, capturing how partial solutions can be arranged on a surface. Then we use singularity analysis over expressions obtained by the symbolic method to prove that partial solutions can be represented by a single-exponential (in the branchwidth k) number of configurations. This proves that, when applied on surface cut decompositions, dynamic programming runs in 2O(k) ċ n steps. That way, we considerably extend the class of problems that can be solved in running times with a single-exponential dependence on branchwidth and unify/improve all previous results in this direction.
Type de document :
Communication dans un congrès
ICALP: International Colloquium on Automata, Languages and Programming, 2010, Bordeaux, France. Springer-Verlag, 37th, pp.372-383, 2010
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00736703
Contributeur : Ignasi Sau <>
Soumis le : vendredi 28 septembre 2012 - 18:09:10
Dernière modification le : vendredi 7 septembre 2018 - 14:04:02

Identifiants

  • HAL Id : lirmm-00736703, version 1

Collections

Citation

Juanjo Rué, Ignasi Sau, Dimitrios M. Thilikos. Dynamic programming for graphs on surfaces. ICALP: International Colloquium on Automata, Languages and Programming, 2010, Bordeaux, France. Springer-Verlag, 37th, pp.372-383, 2010. 〈lirmm-00736703〉

Partager

Métriques

Consultations de la notice

169