Dynamic Programming for H-minor-free Graphs

DOI10.1007/978-3-642-32241-9_8MaRDI QIDQ2914314zbMATH OpenOpenAlexFDO

Authors Juanjo Rué, Ignasi Sau, Dimitrios M. Thilikos

Publication date 25 September 2012

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-32241-9_8

zbMATH Keywords

analysis of algorithmsbranchwidthdynamic programminggraph minorsnon-crossing partitionsparameterized algorithms

Mathematics Subject Classification ID

Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39)

Recommendations

• Catalan structures and dynamic programming in \(H\)-minor-free graphs
• Dynamic programming and d-graphs
• Faster approximation schemes and parameterized algorithms on H-minor-free and odd-minor-free graphs
• Faster approximation schemes and parameterized algorithms on (odd-)H-minor-free graphs
• scientific article; zbMATH DE number 1107726
• Minimum \(H\)-decompositions of graphs
• Graph minors and parameterized algorithm design
• scientific article; zbMATH DE number 4060712
• Dynamic programming for minimum Steiner trees
• Subexponential time algorithms for embedding H-minor free graphs

Cited in

(7)

• Dynamic programming for graphs on surfaces
• Catalan structures and dynamic programming in \(H\)-minor-free graphs
• Coverability and sub-exponential parameterized algorithms in planar graphs
• Contraction-bidimensionality of geometric intersection graphs
• Hitting minors on bounded treewidth graphs. I: General upper bounds
• Dynamic programming for graphs on surfaces
• Contraction bidimensionality of geometric intersection graphs

This page was built for publication: Dynamic Programming for H-minor-free Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2914314)