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)
- A new proof of the flat wall theorem
- Upper bounds on the size of obstructions and intertwines
- On algorithmic applications of the immersion order: An overview of ongoing work presented at the Third Slovenian International Conference on Graph Theory
- String graphs. I: The number of critical nonstring graphs is infinite
- Recognizing a totally odd \(K_{4}\)-subdivision, parity 2-disjoint rooted paths and a parity cycle through specified elements
- Trichotomies in the complexity of minimal inference
- Optimizing adiabatic quantum program compilation using a graph-theoretic framework
- Improved algorithms for finding length-bounded two vertex-disjoint paths in a planar graph and minmax \(k\) vertex-disjoint paths in a directed acyclic graph
- What's next? Future directions in parameterized complexity
- Finding large cycles in Hamiltonian graphs
- Complexity of path-forming games
- Planarizing graphs and their drawings by vertex splitting
- On the complexity of the identifiable subgraph problem
- Alternating paths in edge-colored complete graphs
- Vertex disjoint paths on clique-width bounded graphs
- Some open problems on excluding a uniform matroid
- A \(c^k n\) 5-approximation algorithm for treewidth
- Title not available (Why is that?)
- Square roots of minor closed graph classes
- Disjoint paths in symmetric digraphs
- Processor Efficient Parallel Algorithms for the Two Disjoint Paths Problem and for Finding a Kuratowski Homeomorph
- Linear time parameterized algorithms for subset feedback vertex set
- On the maximum degree of path-pairable planar graphs
- Paths of bounded length and their cuts: parameterized complexity and algorithms
- Paths of bounded length and their cuts: parameterized complexity and algorithms
- Partitioning Graphs into Connected Parts
- Linear kernels for (connected) dominating set on \(H\)-minor-free graphs
- Some recent progress and applications in graph minor theory
- An Improved Algorithm for Finding Cycles Through Elements
- Linear min-max relation between the treewidth of an \(H\)-minor-free graph and its largest grid minor
- Confronting intractability via parameters
- Criticality for multicommodity flows
- Edge-disjoint paths in digraphs with bounded independence number
- Finding a subdivision of a digraph
- String graphs. II: Recognizing string graphs is NP-hard
- Obtaining a Planar Graph by Vertex Deletion
- Finding edge-disjoint paths in partial k-trees
- On the complexity of database queries
- Disjoint paths in tournaments
- Solving the 2-disjoint connected subgraphs problem faster than \(2^n\)
- Complexity evaluation of benchmark instances for the \(p\)-median problem
- On partitioning a graph into two connected subgraphs
- All structured programs have small tree width and good register allocation
- Finding disjoint paths in split graphs
- Computing tree-depth faster than \(2^n\)
- Finding disjoint paths in split graphs
- Multiflow Feasibility: An Annotated Tableau
- The structure of obstructions to treewidth and pathwidth
- Forbidden directed minors and Kelly-width
- Algorithms for finding an induced cycle in planar graphs
- Combinatorial optimization with 2-joins
- Finding edge-disjoint paths in partial \(k\)-trees
- Title not available (Why is that?)
- Quickly deciding minor-closed parameters in general graphs
- The hardness of routing two pairs on one face
- New hardness results for routing on disjoint paths
- Forbidding Kuratowski graphs as immersions
- Note on coloring graphs without odd-\(K_k\)-minors
- List-coloring graphs without subdivisions and without immersions
- Parameterized algorithms for list \(K\)-cycle
- A simple linear-time algorithm for finding path-decompositions of small width
- MSOL restricted contractibility to planar graphs
- 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
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)
