In:
ACM Transactions on Algorithms, Association for Computing Machinery (ACM), Vol. 10, No. 2 ( 2014-02), p. 1-26
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 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 decomposition , 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 noncrossing 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 problems that can be solved in running times with a single-exponential dependence on branchwidth and unify/improve most previous results in this direction.
Type of Medium:
Online Resource
ISSN:
1549-6325
,
1549-6333
Language:
English
Publisher:
Association for Computing Machinery (ACM)
Publication Date:
2014
detail.hit.zdb_id:
2198259-4
Permalink