Graph minors. XXII. Irrelevant vertices in linkage problems

DOI10.1016/j.jctb.2007.12.007zbMath1239.05173OpenAlexW2046069847MaRDI QIDQ412177

Neil Robertson, P. D. 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 minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths, Fixed-Parameter Tractability of Treewidth and Pathwidth, Graph Minors and Parameterized Algorithm Design, Planar disjoint-paths completion, Irrelevant vertices for the planar disjoint paths problem, Some recent progress and applications in graph minor theory, Effective computation of immersion obstructions for unions of graph classes, Adapting the Directed Grid Theorem into an FPT Algorithm, \(k\)-apices of minor-closed graph classes. I: Bounding the obstructions, Embedding graphs in the torus in linear time, Combing a Linkage in an Annulus, The Induced Disjoint Paths Problem, Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm, A linear time algorithm for the induced disjoint paths problem in planar graphs, Fixed-parameter tractability for the subset feedback set problem and the \(S\)-cycle packing problem, Hitting Minors on Bounded Treewidth Graphs. I. General Upper Bounds, Confronting intractability via parameters, Algorithms for finding an induced cycle in planar graphs, Tight Bounds for Linkages in Planar Graphs, The edge-disjoint paths problem in Eulerian graphs and 4-edge-connected graphs, Explicit bounds for graph minors, Linear min-max relation between the treewidth of an \(H\)-minor-free graph and its largest grid minor, The Parameterized Complexity of Graph Cyclability, A partial k-arboretum of graphs with bounded treewidth, A lower bound on the tree-width of graphs with irrelevant vertices, Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness, Unnamed Item, Fixed-parameter tractability for subset feedback set problems with parity constraints

Cites Work

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