Graph minors. XIII: The disjoint paths problem
From MaRDI portal
Publication:1892832
DOI10.1006/JCTB.1995.1006zbMATH Open0823.05038DBLPjournals/jct/RobertsonS95bOpenAlexW2005079828WikidataQ55881137 ScholiaQ55881137MaRDI QIDQ1892832FDOQ1892832
Authors: Neil Robertson, Paul Seymour 
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
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38)
Cited In (only showing first 100 items - show all)
- Routing in undirected graphs with constant congestion
- Searching for an evader in an unknown dark cave by an optimal number of asynchronous searchers
- Packing cycles in undirected group-labelled graphs
- Directed Steiner tree packing and directed tree connectivity
- Disjoint paths in sparse graphs
- Title not available (Why is that?)
- Graph theory. Abstracts from the workshop held January 2--8, 2022
- Size-treewidth tradeoffs for circuits computing the element distinctness function
- Embeddings of graphs
- Graph minors and parameterized algorithm design
- Multiflows in symmetric digraphs
- Slightly superexponential parameterized problems
- Crossing minimization for 1-page and 2-page drawings of graphs with bounded treewidth
- Space-efficient vertex separators for treewidth
- Shortest \((A+B)\)-path packing via hafnian
- Linking four vertices in graphs of large connectivity
- A lower bound for treewidth and its consequences
- Edge disjoint paths and max integral multiflow/min multicut theorems in planar graphs
- On the pathwidth of almost semicomplete digraphs
- Towards tight(er) bounds for the excluded grid theorem
- Detours in directed graphs
- Approximating the maximum clique minor and some subgraph homeomorphism problems
- Cycle lengths in randomly perturbed graphs
- A survey of parameterized algorithms and the complexity of edge modification
- The extremal function for 3-linked graphs
- Shortest node-disjoint paths on random graphs
- An analysis of the parameterized complexity of periodic timetabling
- Recent progress on well-quasi-ordering graphs
- On interval routing schemes and treewidth
- Finding good tree decompositions by local search
- Disjoint Paths—A Survey
- The communication complexity of enumeration, elimination, and selection
- Geodesic geometry on graphs
- On the connectivity of minimum and minimal counterexamples to Hadwiger's conjecture
- Non-approximability and polylogarithmic approximations of the single-sink unsplittable and confluent dynamic flow problems
- Parameters tied to treewidth
- Practical algorithms for branch-decompositions of planar graphs
- Disjoint paths in decomposable digraphs
- Polynomial-time algorithms for the longest induced path and induced disjoint paths problems on graphs of bounded mim-width
- Parameterized computation and complexity: a new approach dealing with NP-hardness
- Faster approximation schemes and parameterized algorithms on (odd-)\(H\)-minor-free graphs
- Modulo orientations and matchings in graphs
- Disjoint paths in graphs. I: 3-planar graphs and basic obstructions
- Wheel-Free Deletion Is W[2]-Hard
- Linkability in iterated line graphs
- The first order definability of graphs with separators via the Ehrenfeucht game
- An exact algorithm for subgraph homeomorphism
- The excluded minors for isometric realizability in the plane
- Title not available (Why is that?)
- An algorithm for detecting intrinsically knotted graphs
- The \(k\)-in-a-path problem for claw-free graphs
- General vertex disjoint paths in series-parallel graphs
- Vertex-minor reductions can simulate edge contractions
- Min-sum 2-paths problems
- Algorithms for finding disjoint path covers in unit interval graphs
- The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
- The complexity of minimum convex coloring
- Satisfiability, branch-width and Tseitin tautologies
- Graphs with the Circuit Cover Property
- Title not available (Why is that?)
- Finding odd cycle transversals.
- Minor-embedding in adiabatic quantum computation. II: Minor-universal graph design
- Tractability in constraint satisfaction problems: a survey
- Edge-disjoint odd cycles in 4-edge-connected graphs
- Minimal multicut and maximal integer multiflow: a survey
- The disjoint paths problem in quadratic time
- A sufficiently fast algorithm for finding close to optimal clique trees
- The edge-disjoint paths problem in Eulerian graphs and 4-edge-connected graphs
- Parallel algorithms with optimal speedup for bounded treewidth
- Minor-embedding in adiabatic quantum computation. I: The parameter setting problem
- Rankings of graphs
- The edge-disjoint paths problem is NP-complete for series-parallel graphs
- Approximation algorithms for treewidth
- A partial k-arboretum of graphs with bounded treewidth
- (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
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Approximate tree decompositions of planar graphs in linear time
- Approximate tree decompositions of planar graphs in linear time
- \(K_{6}\) minors in large 6-connected graphs
- The \(k\)-disjoint paths problem on chordal graphs
- Connectivity and inference problems for temporal networks
- Kernel bounds for disjoint cycles and disjoint paths
- Directed tree-width
- Advice classes of parametrized tractability
- Packing cycles through prescribed vertices under modularity constraints
- Connected graph searching
- Detecting an induced net subdivision
- The 1-fixed-endpoint path cover problem is Polynomial on interval graphs
- Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in \(O(n^{1+\epsilon})\) time
- Small complete minors above the extremal edge density
- The label cut problem with respect to path length and label frequency
- Partitioning graphs into connected parts
- Chordal deletion is fixed-parameter tractable
- Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
- Bounded face-width forces \(K_7\)-minors in orientable surfaces
- A polynomial solution to the \(k\)-fixed-endpoint path cover problem on proper interval graphs
- Coloring immersion-free graphs
This page was built for publication: Graph minors. XIII: The disjoint paths problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1892832)
