TY - GEN

T1 - Catalan structures and dynamic programming in H-minor-free graphs

AU - Dorn, Frederic

AU - Fomin, Fedor V.

AU - Thilikos, Dimitrios M.

PY - 2008

Y1 - 2008

N2 - We give an algorithm that, for a fixed graph H and integer k, decides whether an n-vertex H-minor-free graph G contains a path of length k in 2 O√k · nO(1) steps. Our approach builds on a combination of Demaine-Hajiaghayi's bounds on the size of an excluded grid in such graphs with a novel combinatorial result on certain branch decompositions of H-minor-free graphs. This result is used to bound the number of ways vertex disjoint paths can be routed through the separators of such decompositions. The proof is based on several structural theorems from the Graph Minors series of Robertson and Seymour. With a slight modification, similar combinatorial and algorithmic results can be derived for many other problems. Our approach can be viewed as a general framework for obtaining time 2O√k · nO(1) algorithms on H-minor-free graph classes.

AB - We give an algorithm that, for a fixed graph H and integer k, decides whether an n-vertex H-minor-free graph G contains a path of length k in 2 O√k · nO(1) steps. Our approach builds on a combination of Demaine-Hajiaghayi's bounds on the size of an excluded grid in such graphs with a novel combinatorial result on certain branch decompositions of H-minor-free graphs. This result is used to bound the number of ways vertex disjoint paths can be routed through the separators of such decompositions. The proof is based on several structural theorems from the Graph Minors series of Robertson and Seymour. With a slight modification, similar combinatorial and algorithmic results can be derived for many other problems. Our approach can be viewed as a general framework for obtaining time 2O√k · nO(1) algorithms on H-minor-free graph classes.

UR - http://www.scopus.com/inward/record.url?scp=41249092642&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=41249092642&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:41249092642

SN - 9780898716474

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 631

EP - 640

BT - Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms

T2 - 19th Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 20 January 2008 through 22 January 2008

ER -