A Polynomial Solution to the Undirected Two Paths Problem
From MaRDI portal
Publication:3930654
DOI10.1145/322203.322207zbMath0475.68042OpenAlexW1976285925MaRDI QIDQ3930654
Publication date: 1980
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/322203.322207
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38)
Related Items (85)
Algorithms for finding disjoint path covers in unit interval graphs ⋮ Recoverable robust shortest path problems ⋮ On finding Min-Min disjoint paths ⋮ Rooted routing in the plane ⋮ The complexity of induced minors and related problems ⋮ 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 ⋮ Finding disjoint paths with related path costs ⋮ Characterization of \((m, n)\)-linked planar graphs ⋮ Finding a path with two labels forbidden in group-labeled graphs ⋮ Independent paths and \(K_{5}\)-subdivisions ⋮ On orientations and shortest paths ⋮ Some recent progress and applications in graph minor theory ⋮ When Do Gomory--Hu Subtrees Exist? ⋮ Linking four vertices in graphs of large connectivity ⋮ Projective plan and Möbius band obstructions ⋮ Optimal node disjoint paths on partial 2-trees: A linear algorithm and polyhedral results ⋮ Linear time algorithms for two disjoint paths problems on directed acyclic graphs ⋮ Obstructions for the Disk and the Cylinder Embedding Extension Problems ⋮ Rooted \(K_4\)-minors ⋮ The disjoint shortest paths problem ⋮ 4‐Separations in Hajós graphs ⋮ A hybrid modified-NSGA-II VNS algorithm for the multi-objective critical disruption path problem ⋮ The Induced Disjoint Paths Problem ⋮ Bonds with parity constraints ⋮ A Very Practical Algorithm for the Two-Paths Problem in 3-Connected Planar Graphs ⋮ A graph minor condition for graphs to be \(k\)-linked ⋮ 2-linked graphs ⋮ On the complexity of the edge-disjoint min-min problem in planar digraphs ⋮ On shortest disjoint paths in planar graphs ⋮ Graph theory. Abstracts from the workshop held January 2--8, 2022 ⋮ The 1-fixed-endpoint path cover problem is Polynomial on interval graphs ⋮ A simple solution to the two paths problem in planar graphs ⋮ Symmetric space-bounded computation ⋮ On finding maximum disjoint paths with different colors: computational complexity and practical LP-based algorithms ⋮ Hardness of Finding Two Edge-Disjoint Min-Min Paths in Digraphs ⋮ Optimal parallel algorithms for path problems on planar graphs ⋮ The extremal function for 3-linked graphs ⋮ A new proof of the flat wall theorem ⋮ Links in edge-colored graphs ⋮ General vertex disjoint paths in series-parallel graphs ⋮ Induced disjoint paths problem in a planar digraph ⋮ A linear algorithm for the all-bidirectional-edges problem on planar graphs ⋮ An improved linear edge bound for graph linkages ⋮ 4-connected triangulations and 4-orderedness ⋮ A polynomial solution to the \(k\)-fixed-endpoint path cover problem on proper interval graphs ⋮ The even-path problem for graphs and digraphs ⋮ Determinacy in Linear Systems and Networks ⋮ Improved Algorithms for the 2-Vertex Disjoint Paths Problem ⋮ Unnamed Item ⋮ Shortest \((A+B)\)-path packing via hafnian ⋮ 7-connected graphs are 4-ordered ⋮ On a coloring conjecture of Hajós ⋮ Disjoint paths in symmetric digraphs ⋮ A polynomial-time algorithm to find a linkless embedding of a graph ⋮ Disjoint paths and connected subgraphs for \(H\)-free graphs ⋮ Disjoint paths and connected subgraphs for \(H\)-free graphs ⋮ Two disjoint shortest paths problem with non-negative edge length ⋮ Walking through waypoints ⋮ Theoretical and computational advances for network diversion ⋮ A simpler proof for the two disjoint odd cycles theorem ⋮ The computational complexity of graph contractions II: Two tough polynomially solvable cases ⋮ Graph minors. IX: Disjoint crossed paths ⋮ Structure and recognition of graphs with no 6-wheel subdivision ⋮ On possible counterexamples to Negami's planar cover conjecture ⋮ Graphs with at most one crossing ⋮ 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 ⋮ Shortest Two Disjoint Paths in Polynomial Time ⋮ Rectilinear paths among rectilinear obstacles ⋮ Polynomial algorithms for (integral) maximum two-flows in vertex\(\backslash\)edge-capacitated planar graphs ⋮ The Directed Disjoint Shortest Paths Problem ⋮ Two edge-disjoint paths with length constraints ⋮ The \(\gamma\)-connected assignment problem ⋮ Rooted topological minors on four vertices ⋮ Disjoint Paths—A Survey ⋮ Hadwiger's conjecture for \(K_ 6\)-free graphs ⋮ An approach to the subgraph homeomorphism problem ⋮ Efficient reduction for path problems on circular-arc graphs ⋮ Subdivisions of \(K_5\) in graphs containing \(K_{2,3}\) ⋮ On the Euclidean two paths problem ⋮ Theory of uncontrollable flows -- a new type of network-flow theory as a model for the 21st century of multiple values
This page was built for publication: A Polynomial Solution to the Undirected Two Paths Problem
