Dynamic Programming for Graphs on Surfaces

Details Dynamic Programming for Graphs on Surfaces Dynamic Programming for Graphs on Surfaces

2011-04-13

arxiv.org/abs/1104.2486v4

Computer Science

Data Structures and Algorithms

28 pages, 3 figures

Scientific paper

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 introduced by Seymour and Thomas, 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 problems that can be solved in running times with a single-exponential dependence on branchwidth and unify/improve most previous results in this direction.

Affiliated with

Also associated with

No associations

Rating

Dynamic Programming for Graphs on Surfaces does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Dynamic Programming for Graphs on Surfaces, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dynamic Programming for Graphs on Surfaces will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-218807