A Polynomial Solution to the Undirected Two Paths Problem

Cited in

(91)

Disjoint paths in symmetric digraphs
A polynomial-time algorithm to find a linkless embedding of a graph
Structure and recognition of graphs with no 6-wheel subdivision
An approach to the subgraph homeomorphism problem
On orientations and shortest paths
2-linked graphs
Symmetric space-bounded computation
General vertex disjoint paths in series-parallel graphs
A linear algorithm for the all-bidirectional-edges problem on planar graphs
The -connected assignment problem
Hadwiger's conjecture for \(K_ 6\)-free graphs
On the Euclidean two paths problem
Rooted routing in the plane
The complexity of induced minors and related problems
Projective plan and Möbius band obstructions
The disjoint shortest paths problem
Theory of uncontrollable flows -- a new type of network-flow theory as a model for the 21st century of multiple values
An improved linear edge bound for graph linkages
Graph minors. IX: Disjoint crossed paths
Linear time algorithms for two disjoint paths problems on directed acyclic graphs
The 1-fixed-endpoint path cover problem is Polynomial on interval graphs
Rooted topological minors on four vertices
Characterization of \((m, n)\)-linked planar graphs
On finding maximum disjoint paths with different colors: computational complexity and practical LP-based algorithms
A polynomial solution to the \(k\)-fixed-endpoint path cover problem on proper interval graphs
7-connected graphs are 4-ordered
Two disjoint shortest paths problem with non-negative edge length
Graphs with at most one crossing
Two edge-disjoint paths with length constraints
Subdivisions of \(K_5\) in graphs containing \(K_{2,3}\)
On finding Min-Min disjoint paths
Rectilinear paths among rectilinear obstacles
Polynomial algorithms for (integral) maximum two-flows in vertex\(\backslash\)edge-capacitated planar graphs
Linking four vertices in graphs of large connectivity
Algorithms for finding disjoint path covers in unit interval graphs
Graph theory. Abstracts from the workshop held January 2--8, 2022
Theoretical and computational advances for network diversion
Recoverable robust shortest path problems
Hardness of finding two edge-disjoint Min-Min paths in digraphs
Finding two edge-disjoint paths with length constraints
Non-planar extensions of subdivisions of planar graphs
The structure of graphs not topologically containing the Wagner graph
The even-path problem for graphs and digraphs
Determinacy in Linear Systems and Networks
The Induced Disjoint Paths Problem
A Very Practical Algorithm for the Two-Paths Problem in 3-Connected Planar Graphs
Improved Algorithms for the 2-Vertex Disjoint Paths Problem
The computational complexity of graph contractions II: Two tough polynomially solvable cases
Disjoint Paths—A Survey
Rooted K₄-minors
Bonds with parity constraints
On the complexity of the edge-disjoint min-min problem in planar digraphs
On shortest disjoint paths in planar graphs
Obstructions for the Disk and the Cylinder Embedding Extension Problems
On possible counterexamples to Negami's planar cover conjecture
Optimal node disjoint paths on partial 2-trees: A linear algorithm and polyhedral results
When do Gomory-Hu subtrees exist?
Counting shortest two disjoint paths in cubic planar graphs with an NC algorithm
The Directed Disjoint Shortest Paths Problem
Shortest two disjoint paths in polynomial time
Disjoint paths and connected subgraphs for \(H\)-free graphs
Disjoint paths and connected subgraphs for \(H\)-free graphs
Walking through waypoints
On a coloring conjecture of Hajós
Independent paths and \(K_{5}\)-subdivisions
4‐Separations in Hajós graphs
A hybrid modified-NSGA-II VNS algorithm for the multi-objective critical disruption path problem
A graph minor condition for graphs to be \(k\)-linked
Linkages and removable paths avoiding vertices
Optimal parallel algorithms for path problems on planar graphs
A new proof of the flat wall theorem
On the size of two minimal linkages
Chasing tripods to obtain a rooted subdivision
Rerouting planar curves and disjoint paths
K₅-subdivisions in graphs containing K₄^-
Killing a vortex
4-connected triangulations and 4-orderedness
Shortest \((A+B)\)-path packing via hafnian
Complexity framework for forbidden subgraphs. II: Edge subdivision and the ``H-graphs
A simpler proof for the two disjoint odd cycles theorem
The Kelmans-Seymour conjecture. I: Special separations
The Kelmans-Seymour conjecture. II: 2-vertices in \(K_4^-\)
The Kelmans-Seymour conjecture. III: 3-vertices in \(K_4^-\)
The Kelmans-Seymour conjecture. IV: A proof
Efficient reduction for path problems on circular-arc graphs
Finding disjoint paths with related path costs
Some recent progress and applications in graph minor theory
A simple solution to the two paths problem in planar graphs
The extremal function for 3-linked graphs
Links in edge-colored graphs
Induced disjoint paths problem in a planar digraph

This page was built for publication: A Polynomial Solution to the Undirected Two Paths Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3930654)