The disjoint paths problem in quadratic time

DOI10.1016/j.jctb.2011.07.004zbMath1298.05296OpenAlexW2115589427WikidataQ55934686 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

zbMATH Keywords

graph minortree-widthdisjoint pathsquadratic time

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (65)

Edge-disjoint odd cycles in 4-edge-connected graphs ⋮ Polynomial Time Algorithms for Tracking Path Problems ⋮ Random Walks and Forbidden Minors II: A $\mathrm{poly}(d\varepsilon^{-1})$-Query Tester for Minor-Closed Properties of Bounded-Degree Graphs ⋮ Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths ⋮ Linear Time Parameterized Algorithms for Subset Feedback Vertex Set ⋮ Towards the Graph Minor Theorems for Directed Graphs ⋮ Polynomial time algorithms for tracking path problems ⋮ Graph Minors and Parameterized Algorithm Design ⋮ Coloring immersion-free graphs ⋮ From the \(W\)-hierarchy to XNLP. Classes of fixed parameter intractability ⋮ Finding cycles and trees in sublinear time ⋮ All-or-Nothing Multicommodity Flow Problem with Bounded Fractionality in Planar Graphs ⋮ Simple undirected two-commodity integral flow with a unitary demand ⋮ Solving Matching Problems Efficiently in Bipartite Graphs ⋮ Linear time algorithms for two disjoint paths problems on directed acyclic graphs ⋮ On the maximum degree of path-pairable planar graphs ⋮ Rooted \(K_4\)-minors ⋮ \(k\)-apices of minor-closed graph classes. I: Bounding the obstructions ⋮ Terminal-pairability in complete bipartite graphs with non-bipartite demands. Edge-disjoint paths in complete bipartite graphs ⋮ Parameterizing path partitions ⋮ Combing a Linkage in an Annulus ⋮ Steiner connectivity problems in hypergraphs ⋮ On undirected two‐commodity integral flow, disjoint paths and strict terminal connection problems ⋮ Detours in directed graphs ⋮ A linear time algorithm for the induced disjoint paths problem in planar graphs ⋮ Approximating maximum integral multiflows on bounded genus graphs ⋮ A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs ⋮ Linkless and flat embeddings in 3-space ⋮ Using a Geometric Lens to Find \(\boldsymbol{k}\)-Disjoint Shortest Paths ⋮ Almost disjoint paths and separating by forbidden pairs ⋮ Social disruption games in signed networks ⋮ 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? ⋮ Fixed-parameter tractability for the subset feedback set problem and the \(S\)-cycle packing problem ⋮ Faster parameterized algorithms for minor containment ⋮ Finding k Partially Disjoint Paths in a Directed Planar Graph ⋮ Finding disjoint paths in split graphs ⋮ The edge-disjoint paths problem in Eulerian graphs and 4-edge-connected graphs ⋮ Clique-width and well-quasi-ordering of triangle-free graph classes ⋮ Partitioning a graph into balanced connected classes: formulations, separation and experiments ⋮ Linear min-max relation between the treewidth of an \(H\)-minor-free graph and its largest grid minor ⋮ Claw-Free $t$-Perfect Graphs Can Be Recognized in Polynomial Time ⋮ 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 ⋮ The linkedness of cubical polytopes: the cube ⋮ A polynomial sized kernel for tracking paths problem ⋮ Block elimination distance ⋮ Induced disjoint paths in AT-free graphs ⋮ The directed 2-linkage problem with length constraints ⋮ Using decomposition-parameters for QBF: mind the prefix! ⋮ Random Walks and Forbidden Minors I: An $n^{1/2+o(1)}$-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs ⋮ Random Walks and Forbidden Minors I: An $n^{1/2+o(1)}$-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs ⋮ The complexity of mixed-connectivity ⋮ The Directed Disjoint Shortest Paths Problem ⋮ Structural aspects of semigroups based on digraphs ⋮ Refined parameterizations for computing colored cuts in edge-colored graphs ⋮ A Linear-Time Parameterized Algorithm for Node Unique Label Cover ⋮ Structural parameterizations of Tracking Paths problem ⋮ On the maximum weight minimal separator ⋮ Unnamed Item ⋮ Fixed-parameter tractability for subset feedback set problems with parity constraints

Cites Work

• Unnamed Item
• 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
• 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

This page was built for publication: The disjoint paths problem in quadratic time