Dynamic Programming for Graphs on Surfaces - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Journal Articles ACM Transactions on Algorithms Year : 2014

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 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.
Fichier principal
Vignette du fichier
dprog.pdf (860.38 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

lirmm-01083690 , version 1 (17-11-2014)

Identifiers

Cite

Juanjo Rué, Ignasi Sau, Dimitrios M. Thilikos. Dynamic Programming for Graphs on Surfaces. ACM Transactions on Algorithms, 2014, 10 (2), pp.1-26/8. ⟨10.1145/2556952⟩. ⟨lirmm-01083690⟩
181 View
312 Download

Altmetric

Share

More