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, The complexity of finding two disjoint paths with min-max objective function, Optimal parallel algorithms for path problems on planar graphs, Bounds on path connectivity, A simple solution to the two paths problem in planar graphs, Disjoint paths in symmetric digraphs, Structure and recognition of graphs with no 6-wheel subdivision, Disjoint directed and undirected paths and cycles in digraphs, Embedding ternary trees in VLSI arrays, The directed subgraph homeomorphism problem, The subgraph homeomorphism problem, 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, Hypernetworks in a directed hypergraph, Rectilinear paths among rectilinear obstacles, A Very Practical Algorithm for the Two-Paths Problem in 3-Connected Planar Graphs, Improved Algorithms for the 2-Vertex Disjoint Paths Problem, Finding the k Shortest Paths
