Quickly deciding minor-closed parameters in general graphs

DOI10.1016/J.EJC.2005.07.003MaRDI QIDQ854832zbMATHOpenAlexFDO

Authors Erik D. Demaine, Mohammad T. Hajiaghayi

Publication date 7 December 2006

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ejc.2005.07.003

Mathematics Subject Classification ID

Graph minors (05C83)

Recommendations

• A Faster Shortest-Paths Algorithm for Minor-Closed Graph Classes
• Graph minors and parameterized algorithm design
• The complexity of learning minor closed graph classes
• scientific article; zbMATH DE number 5874803
• k -apices of Minor-closed Graph Classes. II. Parameterized Algorithms
• Fast separation in a graph with an excluded minor
• Exponential speedup of fixed-parameter algorithms for classes of graphs excluding single-crossing graphs as minors
• Optimizing the graph minors weak structure theorem
• Faster parameterized algorithms for minor containment
• Faster parameterized algorithms for minor containment

Cites work

• scientific article; zbMATH DE number 4033746 (Why is no real title available?)
• scientific article; zbMATH DE number 1142315 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• Bidimensional Parameters and Local Treewidth
• Bidimensionality: new connections between FPT algorithms and PTASs
• Deciding first-order properties of locally tree-decomposable structures
• Graph minors. XII: Distance on a surface
• Graph minors. XIII: The disjoint paths problem
• Graph minors. XX: Wagner's conjecture
• Nonconstructive tools for proving polynomial-time decidability
• Quickly excluding a planar graph
• Subexponential parameterized algorithms on graphs of bounded-genus and \(H\)-minor-free graphs

Cited in

(5)

• Polynomial treewidth forces a large grid-like-minor
• Faster parameterized algorithms for minor containment
• Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction
• Towards tight(er) bounds for the excluded grid theorem
• The complexity of learning minor closed graph classes

This page was built for publication: Quickly deciding minor-closed parameters in general graphs

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