Graph minors. XIII: The disjoint paths problem
From MaRDI portal
Publication:1892832
DOI10.1006/JCTB.1995.1006zbMath0823.05038DBLPjournals/jct/RobertsonS95bOpenAlexW2005079828WikidataQ55881137 ScholiaQ55881137MaRDI QIDQ1892832
Publication date: 2 July 1995
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jctb.1995.1006
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (only showing first 100 items - show all)
\(k\)-apices of minor-closed graph classes. I: Bounding the obstructions ⋮ Packing cycles in undirected group-labelled graphs ⋮ Kernelization of arc disjoint cycle packing in \(\alpha\)-bounded digraphs ⋮ The complexity of contracting bipartite graphs into small cycles ⋮ Induced disjoint paths and connected subgraphs for \(H\)-free graphs ⋮ Induced disjoint paths and connected subgraphs for \(H\)-free graphs ⋮ Parameterizing path partitions ⋮ Combing a Linkage in an Annulus ⋮ On the bond polytope ⋮ Cycle lengths in randomly perturbed graphs ⋮ On the complexity of the bilevel minimum spanning tree problem ⋮ The firebreak problem ⋮ Solving the edge‐disjoint paths problem using a two‐stage method ⋮ Edge-treewidth: algorithmic and combinatorial properties ⋮ Steiner connectivity problems in hypergraphs ⋮ Optimal sufficient requirements on the embedded Ising problem in polynomial time ⋮ First-order Logic with Connectivity Operators ⋮ Tangle bases: Revisited ⋮ On undirected two‐commodity integral flow, disjoint paths and strict terminal connection problems ⋮ Arkhipov's theorem, graph minors, and linear system nonlocal games ⋮ Directed Steiner tree packing and directed tree connectivity ⋮ Detours in directed graphs ⋮ Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm ⋮ On Interval Routing Schemes and treewidth ⋮ Packing topological minors half‐integrally ⋮ On the logical strength of the better quasi order with three elements ⋮ Approximating maximum integral multiflows on bounded genus graphs ⋮ Excluding a planar matching minor in bipartite graphs ⋮ A graph minor condition for graphs to be \(k\)-linked ⋮ A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Multi-parameter analysis of finding minors and subgraphs in edge-periodic temporal graphs ⋮ Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space ⋮ How to build a pillar: a proof of Thomassen's conjecture ⋮ Using a Geometric Lens to Find \(\boldsymbol{k}\)-Disjoint Shortest Paths ⋮ Planarizing graphs and their drawings by vertex splitting ⋮ The linkedness of cubical polytopes: beyond the cube ⋮ A lower bound for treewidth and its consequences ⋮ Rankings of graphs ⋮ A unified half‐integral Erdős–Pósa theorem for cycles in graphs labelled by multiple abelian groups ⋮ Almost disjoint paths and separating by forbidden pairs ⋮ Minor embedding in broken chimera and derived graphs is NP-complete ⋮ Unnamed Item ⋮ Contracting to a longest path in H-free graphs ⋮ Few induced disjoint paths for \(H\)-free graphs ⋮ Finding edge-disjoint paths in partial k-trees ⋮ Vertex-minors of graphs: a survey ⋮ Parameterized Complexity of Vertex Splitting to Pathwidth at Most 1 ⋮ An improved parameterized algorithm for treewidth ⋮ Sparse graphs with bounded induced cycle packing number have logarithmic treewidth ⋮ Parameterized algorithms for finding highly connected solution ⋮ Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable ⋮ Algorithms for finding disjoint path covers in unit interval graphs ⋮ Chordless paths through three vertices ⋮ Searching for an evader in an unknown dark cave by an optimal number of asynchronous searchers ⋮ Tractability in constraint satisfaction problems: a survey ⋮ Edge-disjoint odd cycles in 4-edge-connected graphs ⋮ Cyclability in graph classes ⋮ (Total) vector domination for graphs with bounded branchwidth ⋮ Excluded-minor characterization of apex-outerplanar graphs ⋮ Contraction obstructions for connected graph searching ⋮ Computing directed pathwidth in \(O(1.89^n)\) time ⋮ Approximate tree decompositions of planar graphs in linear time ⋮ Small complete minors above the extremal edge density ⋮ The label cut problem with respect to path length and label frequency ⋮ Approximation algorithms for treewidth ⋮ Bounded face-width forces \(K_7\)-minors in orientable surfaces ⋮ Coloring immersion-free graphs ⋮ Planar disjoint-paths completion ⋮ Quickly deciding minor-closed parameters in general graphs ⋮ Differential geometric treewidth estimation in adiabatic quantum computation ⋮ On the connectivity of minimum and minimal counterexamples to Hadwiger's conjecture ⋮ Reducing rank of the adjacency matrix by graph modification ⋮ Graph editing to a fixed target ⋮ Irrelevant vertices for the planar disjoint paths problem ⋮ On the Hadwiger's conjecture for graph products ⋮ Some recent progress and applications in graph minor theory ⋮ The density maximization problem in graphs ⋮ Detecting induced minors in AT-free graphs ⋮ Kernel bounds for path and cycle problems ⋮ Parameterized complexity of vertex deletion into perfect graph classes ⋮ Effective computation of immersion obstructions for unions of graph classes ⋮ Rooted \(K_4\)-minors ⋮ Immersion in four-edge-connected graphs ⋮ Practical algorithms for branch-decompositions of planar graphs ⋮ The disjoint paths problem in quadratic time ⋮ Graph minors. XXII. Irrelevant vertices in linkage problems ⋮ A linear time algorithm for the induced disjoint paths problem in planar graphs ⋮ On graph contractions and induced minors ⋮ The complexity of minimum convex coloring ⋮ Linkless and flat embeddings in 3-space ⋮ Edge contractions in subclasses of chordal graphs ⋮ A combinatorial optimization algorithm for solving the branchwidth problem ⋮ Graph operations on parity games and polynomial-time algorithms ⋮ On shortest disjoint paths in planar graphs ⋮ Satisfiability, branch-width and Tseitin tautologies ⋮ Complexity evaluation of benchmark instances for the \(p\)-median problem ⋮ On the maximum disjoint paths problem on edge-colored graphs ⋮ Kernel bounds for disjoint cycles and disjoint paths ⋮ Fixed-parameter tractability for the subset feedback set problem and the \(S\)-cycle packing problem
This page was built for publication: Graph minors. XIII: The disjoint paths problem
