Finding Two Disjoint Paths Between Two Pairs of Vertices in a Graph
From MaRDI portal
Publication:4140364
DOI10.1145/322047.322048zbMath0365.68026MaRDI QIDQ4140364
Publication date: 1978
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/322047.322048
68Q25: Analysis of algorithms and problem complexity
05C35: Extremal problems in graph theory
05C20: Directed graphs (digraphs), tournaments
68W99: Algorithms in computer science
Related Items
Balanced paths in acyclic networks: Tractable cases and related approaches, Optimal node disjoint paths on partial 2-trees: A linear algorithm and polyhedral results, Optimal parallel algorithms for path problems on planar graphs, The point-to-point delivery and connection problems: Complexity and algorithms, A linear algorithm for the all-bidirectional-edges problem on planar graphs, Strictly-upward drawings of ordered search trees, Advances in the theory and practice of graph drawing, On the Euclidean two paths problem, A linear algorithm for 2-bend embeddings of planar graphs in the two-dimensional grid, Linear area upward drawings of AVL trees, 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, Length-bounded disjoint paths in planar graphs, Rectilinear paths among rectilinear obstacles, Finding the k Shortest Paths