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 minor tree-width disjoint paths quadratic 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

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