The disjoint paths problem in quadratic time
From MaRDI portal
Publication:412168
DOI10.1016/J.JCTB.2011.07.004zbMATH Open1298.05296DBLPjournals/jct/KawarabayashiKR12OpenAlexW2115589427WikidataQ55934686 ScholiaQ55934686MaRDI QIDQ412168FDOQ412168
Authors: Ken-ichi Kawarabayashi, Yusuke Kobayashi, Bruce Reed 
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.2011.07.004
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Graph minors (05C83)
Cites Work
- Title not available (Why is that?)
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Graph minors. XIII: The disjoint paths problem
- Title not available (Why is that?)
- Graph minors. V. Excluding a planar graph
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- Disjoint paths in graphs
- 2-linked graphs
- Highly connected sets and the excluded grid theorem
- Quickly excluding a planar graph
- A shorter proof of the graph minor algorithm: the unique linkage theorem
- Graph minors. II. Algorithmic aspects of tree-width
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the complexity of the disjoint paths problem
- On the Computational Complexity of Combinatorial Problems
- S-functions for graphs
- A linear-time algorithm to find a separator in a graph excluding a minor
- Graph minors. XXI. graphs with unique linkages
- Title not available (Why is that?)
- An improved algorithm for finding tree decompositions of small width
- Graph minors. XVI: Excluding a non-planar graph
- Title not available (Why is that?)
- A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
- Solving the 2-disjoint paths problem in nearly linear time
- The all-or-nothing multicommodity flow problem
- Multicommodity flow, well-linked terminals, and routing problems
- Approximations for the disjoint paths problem in high-diameter planar networks
- Rooted routing in the plane
- Edge-disjoint paths in planar graphs with constant congestion
- Title not available (Why is that?)
- Improved Algorithms for the 2-Vertex Disjoint Paths Problem
- Title not available (Why is that?)
- Title not available (Why is that?)
- Coloring triangle-free graphs on surfaces
Cited In (77)
- Induced disjoint paths in AT-free graphs
- A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs
- Rooted \(K_4\)-minors
- The Directed Disjoint Shortest Paths Problem
- A polynomial sized kernel for tracking paths problem
- Structural aspects of semigroups based on digraphs
- Title not available (Why is that?)
- Clique-width and well-quasi-ordering of triangle-free graph classes
- Title not available (Why is that?)
- Edge-disjoint odd cycles in 4-edge-connected graphs
- STACS 2004
- Linkless and flat embeddings in 3-space
- The edge-disjoint paths problem in Eulerian graphs and 4-edge-connected graphs
- \(k\)-apices of minor-closed graph classes. I: Bounding the obstructions
- Graph minors and parameterized algorithm design
- The linkedness of cubical polytopes: the cube
- Fixed-parameter tractability for subset feedback set problems with parity constraints
- FPT and kernelization algorithms for the induced tree problem
- Constant factor approximation for tracking paths and fault tolerant feedback vertex set
- Fixed-parameter tractability for the subset feedback set problem and the \(S\)-cycle packing problem
- Detours in directed graphs
- Polynomial time algorithms for tracking path problems
- Partitioning a graph into balanced connected classes: formulations, separation and experiments
- Solving matching problems efficiently in bipartite graphs
- A tight lower bound for edge-disjoint paths on planar DAGs
- All-or-nothing multicommodity flow problem with bounded fractionality in planar graphs
- Linear time parameterized algorithms for subset feedback vertex set
- Random walks and forbidden minors. I: An \(n^{1/2+o(1)}\)-query one-sided tester for minor closed properties on bounded degree graphs
- On the maximum degree of path-pairable planar graphs
- Title not available (Why is that?)
- From the \(W\)-hierarchy to XNLP. Classes of fixed parameter intractability
- Coloring immersion-free graphs
- Linear min-max relation between the treewidth of an \(H\)-minor-free graph and its largest grid minor
- Linear time algorithms for two disjoint paths problems on directed acyclic graphs
- Using a Geometric Lens to Find \(\boldsymbol{k}\)-Disjoint Shortest Paths
- Finding \(k\) partially disjoint paths in a directed planar graph
- Faster parameterized algorithms for minor containment
- Combing a Linkage in an Annulus
- A linear time algorithm for the induced disjoint paths problem in planar graphs
- On the complexity of the disjoint paths problem
- Erdős-Pósa property and its algorithmic applications: parity constraints, subset feedback set, and subset packing
- Finding cycles and trees in sublinear time
- On the maximum weight minimal separator
- Disjoint paths and connected subgraphs for \(H\)-free graphs
- Disjoint paths and connected subgraphs for \(H\)-free graphs
- Towards the graph minor theorems for directed graphs
- Finding disjoint paths in split graphs
- The complexity of mixed-connectivity
- Structural parameterizations of Tracking Paths problem
- Claw-free \(t\)-perfect graphs can be recognized in polynomial time
- Can local optimality be used for efficient data reduction?
- The directed 2-linkage problem with length constraints
- Using decomposition-parameters for QBF: mind the prefix!
- Refined parameterizations for computing colored cuts in edge-colored graphs
- Simple undirected two-commodity integral flow with a unitary demand
- Polynomial Time Algorithms for Tracking Path Problems
- Terminal-pairability in complete bipartite graphs with non-bipartite demands. Edge-disjoint paths in complete bipartite graphs
- Block elimination distance
- Block elimination distance
- Approximating maximum integral multiflows on bounded genus graphs
- Dichotomies for tree minor containment with structural parameters
- A Linear-Time Parameterized Algorithm for Node Unique Label Cover
- Faster parameterized algorithms for modification problems to minor-closed classes
- A more accurate view of the flat wall theorem
- Steiner connectivity problems in hypergraphs
- Almost disjoint paths and separating by forbidden pairs
- Social disruption games in signed networks
- Random Walks and Forbidden Minors I: An $n^{1/2+o(1)}$-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs
- Constant factor approximation for tracking paths and fault tolerant feedback vertex set
- Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths
- On undirected two‐commodity integral flow, disjoint paths and strict terminal connection problems
- Blazing a trail via matrix multiplications: a faster algorithm for non-shortest induced paths
- Dichotomies for tree minor containment with structural parameters
- Parameterizing path partitions
- Parameterizing path partitions
- A constant-factor approximation for weighted bond cover
- Random Walks and Forbidden Minors II: A $\mathrm{poly}(d\varepsilon^{-1})$-Query Tester for Minor-Closed Properties of Bounded-Degree Graphs
This page was built for publication: The disjoint paths problem in quadratic time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q412168)
