Dynamic Programming for Graphs on Surfaces

Juanjo Rué 1 Ignasi Sau 2 Dimitrios M. Thilikos 2, 3
2 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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 stan-dard dynamic programming runs in 2 O(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 decom-position, generalizing sphere cut decompositions of planar graphs which has nice combinatorial properties. Namely, the number of partial solutions that can be arranged on a surface cut decomposition can be upper-bounded by the number of non-crossing partitions on surfaces with boundary. It follows 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 2 O(k) · n steps. That way, we considerably extend the class of prob-lems that can be solved in running times with a single-exponential dependence on branchwidth and unify/improve most previous results in this direction.
Type de document :
Article dans une revue
ACM Transactions on Algorithms, Association for Computing Machinery, 2014, 10 (2), pp.Article No. 8. 〈10.1145/2556952〉
Liste complète des métadonnées

Littérature citée [32 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01083690
Contributeur : Dimitrios M. Thilikos <>
Soumis le : lundi 17 novembre 2014 - 16:55:10
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13
Document(s) archivé(s) le : vendredi 14 avril 2017 - 13:57:30

Fichier

dprog.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Juanjo Rué, Ignasi Sau, Dimitrios M. Thilikos. Dynamic Programming for Graphs on Surfaces. ACM Transactions on Algorithms, Association for Computing Machinery, 2014, 10 (2), pp.Article No. 8. 〈10.1145/2556952〉. 〈lirmm-01083690〉

Partager

Métriques

Consultations de la notice

85

Téléchargements de fichiers

163