Subexponential time algorithms for embedding H-minor free graphs

DOI10.4230/LIPICS.ICALP.2016.9MaRDI QIDQ4598141zbMATH OpenOpenAlexFDO

Authors Jesper Nederlof, Tom C. van der Zanden, Hans L. Bodlaender

Publication date 19 December 2017

Full work available at URL https://doi.org/10.4230/lipics.icalp.2016.9

zbMATH Keywords

subexponential timegraph minorssubgraph isomorphism

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph minors (05C83)

Recommendations

• Fast minor testing in planar graphs
• Subexponential parameterized algorithms on graphs of bounded-genus and \(H\)-minor-free graphs
• Subexponential parameterized algorithms on bounded-genus graphs and \(H\)-minor-free graphs
• Improved lower bounds for graph embedding problems
• Planar subgraph isomorphism revisited

Cited in

(12)

• A subexponential parameterized algorithm for directed subset traveling salesman problem on planar graphs
• Tight lower bounds on graph embedding problems
• Games, Puzzles and Treewidth
• Fast minor testing in planar graphs
• On the exact complexity of polyomino packing
• On the exact complexity of polyomino packing
• Enumerating grid layouts of graphs
• Dynamic Programming for H-minor-free Graphs
• Subgraph isomorphism on graph classes that exclude a substructure
• Algorithms and Turing kernels for detecting and counting small patterns in unit disk graphs
• Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering
• Improved lower bounds for graph embedding problems

This page was built for publication: Subexponential time algorithms for embedding \(H\)-minor free graphs

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