Faster parameterized algorithms for minor containment

DOI10.1016/j.tcs.2011.09.015zbMath1228.68035OpenAlexW1989055377WikidataQ60488564 ScholiaQ60488564MaRDI QIDQ650942

Ignasi Sau, Isolde Adler, Frederic Dorn, Fedor V. Fomin, Dimitrios M. Thilikos

Publication date: 7 December 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.09.015

zbMATH Keywords

dynamic programmingparameterized complexitygraph minorsgraphs on surfacesbranchwidthgraph minor containment

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39) Graph minors (05C83)

Related Items

Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths ⋮ Differential geometric treewidth estimation in adiabatic quantum computation ⋮ Systematic and deterministic graph minor embedding for Cartesian products of graphs ⋮ Graph minors from simulated annealing for annealing machines with sparse connectivity ⋮ Minor embedding in broken chimera and derived graphs is NP-complete ⋮ Hitting Minors on Bounded Treewidth Graphs. I. General Upper Bounds ⋮ Adiabatic quantum programming: minor embedding with hard faults ⋮ Explicit linear kernels for packing problems ⋮ Hitting forbidden induced subgraphs on bounded treewidth graphs ⋮ Hitting Forbidden Induced Subgraphs on Bounded Treewidth Graphs ⋮ Hard combinatorial problems and minor embeddings on lattice graphs ⋮ Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The disjoint paths problem in quadratic time
• Subexponential parameterized algorithms
• Graph minors. XX: Wagner's conjecture
• Subexponential parameterized algorithms for degree-constrained subgraph problems on planar graphs
• On the complexity of finding iso- and other morphisms for partial \(k\)- trees
• Call routing and the ratcatcher
• Quickly excluding a planar graph
• Graph minors. XIII: The disjoint paths problem
• Improved bounds on the planar branchwidth with respect to the largest grid minor size
• Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions
• The graph genus problem is NP-complete
• Planar Subgraph Isomorphism Revisited
• Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
• Fast Minor Testing in Planar Graphs
• Dynamic Programming for Graphs on Surfaces
• Nonconstructive tools for proving polynomial-time decidability
• Branch decompositions and minor containment
• Subgraph Isomorphism in Planar Graphs and Related Problems
• Hadwiger's conjecture is decidable
• Fast Subexponential Algorithm for Non-local Problems on Graphs of Bounded Genus

This page was built for publication: Faster parameterized algorithms for minor containment