Recommendations
Cites work
- 2-linked graphs
- A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- A linear-time algorithm to find a separator in a graph excluding a minor
- A shorter proof of the graph minor algorithm: the unique linkage theorem
- Algorithms for finding an induced cycle in planar graphs and bounded genus graphs
- An improved algorithm for finding tree decompositions of small width
- Approximations for the disjoint paths problem in high-diameter planar networks
- Coloring triangle-free graphs on surfaces
- Disjoint paths in graphs
- Edge-disjoint paths in planar graphs with constant congestion
- Graph minors. II. Algorithmic aspects of tree-width
- Graph minors. V. Excluding a planar graph
- Graph minors. XIII: The disjoint paths problem
- Graph minors. XVI: Excluding a non-planar graph
- Graph minors. XXI. graphs with unique linkages
- Highly connected sets and the excluded grid theorem
- scientific article; zbMATH DE number 5764892 (Why is no real title available?)
- scientific article; zbMATH DE number 3936534 (Why is no real title available?)
- scientific article; zbMATH DE number 16298 (Why is no real title available?)
- scientific article; zbMATH DE number 16300 (Why is no real title available?)
- scientific article; zbMATH DE number 1261807 (Why is no real title available?)
- scientific article; zbMATH DE number 475595 (Why is no real title available?)
- scientific article; zbMATH DE number 1057879 (Why is no real title available?)
- scientific article; zbMATH DE number 1775441 (Why is no real title available?)
- Improved Algorithms for the 2-Vertex Disjoint Paths Problem
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- Multicommodity flow, well-linked terminals, and routing problems
- On the complexity of the disjoint paths problem
- On the Computational Complexity of Combinatorial Problems
- Quickly excluding a planar graph
- Rooted routing in the plane
- S-functions for graphs
- Solving the 2-disjoint paths problem in nearly linear time
- The all-or-nothing multicommodity flow problem
Cited in
(99)- Graph minors. XIII: The disjoint paths problem
- 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
- 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
- On the complexity of the disjoint paths problem
- 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?
- scientific article; zbMATH DE number 1629971 (Why is no real title available?)
- Edge-disjoint odd cycles in 4-edge-connected graphs
- 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
- Coloring immersion-free 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
- Rooted K₄-minors
- scientific article; zbMATH DE number 16300 (Why is no real title available?)
- 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
- All-or-nothing multicommodity flow problem with bounded fractionality in planar graphs
- scientific article; zbMATH DE number 219251 (Why is no real title available?)
- Finding disjoint paths in split 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
- The edge-disjoint paths problem in Eulerian graphs and 4-edge-connected graphs
- STACS 2004
- Erdős-Pósa property and its algorithmic applications: parity constraints, subset feedback set, and subset packing
- Random Walks and Forbidden Minors II: A $\mathrm{poly}(d\varepsilon^{-1})$-Query Tester for Minor-Closed Properties of Bounded-Degree Graphs
- Clique-width and well-quasi-ordering of triangle-free graph classes
- Disjoint paths and connected subgraphs for \(H\)-free graphs
- Constant factor approximation for tracking paths and fault tolerant feedback vertex set
- Disjoint paths and connected subgraphs for \(H\)-free graphs
- Block elimination distance
- A polynomial sized kernel for tracking paths problem
- Block elimination distance
- Constant factor approximation for tracking paths and fault tolerant feedback vertex set
- 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
- On undirected two‐commodity integral flow, disjoint paths and strict terminal connection problems
- Detours in directed 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
- Approximating maximum integral multiflows on bounded genus graphs
- A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs
- 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
- Faster parameterized algorithms for minor containment
- Dichotomies for tree minor containment with structural parameters
- Faster parameterized algorithms for modification problems to minor-closed classes
- A more accurate view of the flat wall theorem
- 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
- A constant-factor approximation for weighted bond cover
- An FPT-algorithm for recognizing k-apices of minor-closed graph classes
- Delineating half-integrality of the Erdős-Pósa property for minors: the case of surfaces
- Detecting disjoint shortest paths in linear time and more
- Min-sum disjoint paths on subclasses of chordal graphs
- Kernels for the disjoint paths problem on subclasses of chordal graphs
- Graph parameters, universal obstructions, and WQO
- Decremental sensitivity oracles for covering and packing minors
- The distributed complexity of locally checkable labeling problems beyond paths and trees
- Graph theory. Abstracts from the workshop held January 5--10, 2025
- Kernels for the disjoint paths problem on subclasses of chordal graphs
- The parameterised complexity of integer multicommodity flow
- Vertex identification to a forest
- The minimum clique routing problem on cycles
- Min-sum disjoint paths on subclasses of chordal graphs
- An exponential time parameterized algorithm for planar disjoint paths
- Can local optimality be used for efficient data reduction?
- Lower bounds for approximate (\& exact) \(k\)-\textsc{Disjoint-Shortest-Paths}
- Using a geometric Lens to find k disjoint shortest paths
- A polynomial time algorithm for Steiner tree when terminals avoid a rooted K₄-minor
- Constant approximating disjoint paths on acyclic digraphs is W[1]-hard
- Does subset sum admit short proofs?
- Improved algorithms for perfect graphs and odd holes
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)
