The disjoint paths problem in quadratic time
From MaRDI portal
Publication:412168
DOI10.1016/j.jctb.2011.07.004zbMath1298.05296WikidataQ55934686 ScholiaQ55934686MaRDI QIDQ412168
Ken-ichi Kawarabayashi, Yusuke Kobayashi, Bruce A. 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
68Q25: Analysis of algorithms and problem complexity
05C38: Paths and cycles
05C83: Graph minors
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
All-or-Nothing Multicommodity Flow Problem with Bounded Fractionality in Planar Graphs, Polynomial Time Algorithms for Tracking Path Problems, Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths, The Directed Disjoint Shortest Paths Problem, A Linear-Time Parameterized Algorithm for Node Unique Label Cover, Unnamed Item, Clique-width and well-quasi-ordering of triangle-free graph classes, Disjoint paths and connected subgraphs for \(H\)-free graphs, Disjoint paths and connected subgraphs for \(H\)-free graphs, Constant factor approximation for tracking paths and fault tolerant feedback vertex set, Block elimination distance, Constant factor approximation for tracking paths and fault tolerant feedback vertex set, A polynomial sized kernel for tracking paths problem, Block elimination distance, Random Walks and Forbidden Minors II: A $\mathrm{poly}(d\varepsilon^{-1})$-Query Tester for Minor-Closed Properties of Bounded-Degree Graphs, \(k\)-apices of minor-closed graph classes. I: Bounding the obstructions, Parameterizing path partitions, Combing a Linkage in an Annulus, Steiner connectivity problems in hypergraphs, Detours in directed graphs, A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs, Using a Geometric Lens to Find \(\boldsymbol{k}\)-Disjoint Shortest Paths, Edge-disjoint odd cycles in 4-edge-connected graphs, Coloring immersion-free graphs, Rooted \(K_4\)-minors, A linear time algorithm for the induced disjoint paths problem in planar graphs, Linkless and flat embeddings in 3-space, Fixed-parameter tractability for the subset feedback set problem and the \(S\)-cycle packing problem, Finding disjoint paths in split graphs, The edge-disjoint paths problem in Eulerian graphs and 4-edge-connected graphs, Faster parameterized algorithms for minor containment, Linear time algorithms for two disjoint paths problems on directed acyclic graphs, Partitioning a graph into balanced connected classes: formulations, separation and experiments, The linkedness of cubical polytopes: the cube, Induced disjoint paths in AT-free graphs, The complexity of mixed-connectivity, Refined parameterizations for computing colored cuts in edge-colored graphs, Structural parameterizations of Tracking Paths problem, Polynomial time algorithms for tracking path problems, From the \(W\)-hierarchy to XNLP. Classes of fixed parameter intractability, Linear min-max relation between the treewidth of an \(H\)-minor-free graph and its largest grid minor, The directed 2-linkage problem with length constraints, Using decomposition-parameters for QBF: mind the prefix!, Structural aspects of semigroups based on digraphs, On the maximum weight minimal separator, Fixed-parameter tractability for subset feedback set problems with parity constraints, Simple undirected two-commodity integral flow with a unitary demand, On the maximum degree of path-pairable planar graphs, Terminal-pairability in complete bipartite graphs with non-bipartite demands. Edge-disjoint paths in complete bipartite graphs, FPT and kernelization algorithms for the induced tree problem, A tight lower bound for edge-disjoint paths on planar DAGs, Can local optimality be used for efficient data reduction?, Claw-Free $t$-Perfect Graphs Can Be Recognized in Polynomial Time, Graph Minors and Parameterized Algorithm Design, Finding cycles and trees in sublinear time, Solving Matching Problems Efficiently in Bipartite Graphs, Finding k Partially Disjoint Paths in a Directed Planar Graph, Random Walks and Forbidden Minors I: An $n^{1/2+o(1)}$-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs, Linear Time Parameterized Algorithms for Subset Feedback Vertex Set, Towards the Graph Minor Theorems for Directed Graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Graph minors. XXI. graphs with unique linkages
- 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
- A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
- S-functions for graphs
- Approximations for the disjoint paths problem in high-diameter planar networks
- Highly connected sets and the excluded grid theorem
- Quickly excluding a planar graph
- Rooted routing in the plane
- Graph minors. XVI: Excluding a non-planar graph
- Graph minors. XIII: The disjoint paths problem
- On the complexity of the disjoint paths problem
- Solving the 2-disjoint paths problem in nearly linear time
- A shorter proof of the graph minor algorithm
- A linear-time algorithm to find a separator in a graph excluding a minor
- Edge-disjoint paths in Planar graphs with constant congestion
- The all-or-nothing multicommodity flow problem
- Multicommodity flow, well-linked terminals, and routing problems
- Improved Algorithms for the 2-Vertex Disjoint Paths Problem
- Graph minors. II. Algorithmic aspects of tree-width
- On the Computational Complexity of Combinatorial Problems
- AN IMPROVED ALGORITHM FOR FINDING TREE DECOMPOSITIONS OF SMALL WIDTH
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
