Loading...
Loading...

Go to the content (press return)

Dynamic programming for graphs on surfaces

Author
Rue, J.; Sau, I.; Thilikos, D.
Type of activity
Journal article
Journal
ACM transactions on algorithms
Date of publication
2014-02-01
Volume
10
Number
2
DOI
https://doi.org/10.1145/2556952 Open in new window
Repository
http://hdl.handle.net/2117/86631 Open in new window
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, generalizing sphere cut decompositions of...
Citation
Rue, J., Sau, I., Thilikos, D. Dynamic programming for graphs on surfaces. "ACM transactions on algorithms", 01 Febrer 2014, vol. 10, núm. 2.
Keywords
analysis of algorithms, branchwidth, dynamic programming, graphs on surfaces, noncrossing partitions, parameterized algorithms, polyhedral embeddings
Group of research
GAPCOMB - Geometric, Algebraic and Probabilistic Combinatorics

Participants

Attachments