Graph minors. XXII. Irrelevant vertices in linkage problems

DOI10.1016/J.JCTB.2007.12.007MaRDI QIDQ412177zbMATH OpenOpenAlexFDO

Authors Neil Robertson, Paul Seymour

Publication date 4 May 2012

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jctb.2007.12.007

zbMATH Keywords

graph minorsdisjoint paths algorithmirrelevant vertexlinkage problem

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph minors (05C83)

Recommendations

• Irrelevant vertices for the planar disjoint paths problem
• Graph minors. XIII: The disjoint paths problem
• Graph minors. VI. Disjoint paths across a disc
• Tight bounds for linkages in planar graphs
• scientific article; zbMATH DE number 16300

Cites work

• Graph minors. VI. Disjoint paths across a disc
• Graph minors. VII: Disjoint paths on a surface
• Graph minors. X: Obstructions to tree-decomposition
• Graph minors. XII: Distance on a surface
• Graph minors. XIII: The disjoint paths problem
• Graph minors. XIV: Extending an embedding
• Graph minors. XXI. graphs with unique linkages
• Graph searching and a min-max theorem for tree-width

Cited in

(29)

• The edge-disjoint paths problem in Eulerian graphs and 4-edge-connected graphs
• Confronting intractability via parameters
• Hitting minors on bounded treewidth graphs. I: General upper bounds
• Irrelevant vertices for the planar disjoint paths problem
• Erdős-Pósa property and its algorithmic applications: parity constraints, subset feedback set, and subset packing
• The Induced Disjoint Paths Problem
• Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm
• \(k\)-apices of minor-closed graph classes. I: Bounding the obstructions
• Combing a Linkage in an Annulus
• Fixed-parameter tractability for subset feedback set problems with parity constraints
• A more accurate view of the flat wall theorem
• Tight bounds for linkages in planar graphs
• Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths
• Faster parameterized algorithms for modification problems to minor-closed classes
• Fixed-parameter tractability for the subset feedback set problem and the \(S\)-cycle packing problem
• Some recent progress and applications in graph minor theory
• Graph minors. XXI. graphs with unique linkages
• Graph minors and parameterized algorithm design
• Embedding graphs in the torus in linear time
• Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness
• A partial k-arboretum of graphs with bounded treewidth
• A linear time algorithm for the induced disjoint paths problem in planar graphs
• Fixed-parameter tractability of treewidth and pathwidth
• Planar disjoint-paths completion
• Linear min-max relation between the treewidth of an \(H\)-minor-free graph and its largest grid minor
• Algorithms for finding an induced cycle in planar graphs
• A lower bound on the tree-width of graphs with irrelevant vertices
• Lossy planarization: a constant-factor approximate kernelization for planar vertex deletion
• Adapting the directed grid theorem into an FPT algorithm

This page was built for publication: Graph minors. XXII. Irrelevant vertices in linkage problems

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