Finding Two Disjoint Paths Between Two Pairs of Vertices in a Graph
From MaRDI portal
Publication:4140364
DOI10.1145/322047.322048zbMath0365.68026OpenAlexW1967565181MaRDI 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
Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Directed graphs (digraphs), tournaments (05C20) Algorithms in computer science (68W99)
Related Items
Length-bounded disjoint paths in planar graphs, Multicriteria movement synchronization scheduling problems and algorithms, An efficient algorithm for \(k\)-pairwise disjoint paths in star graphs, On finding Min-Min disjoint paths, Embedding ternary trees in VLSI arrays, Arc-Disjoint Paths in Decomposable Digraphs, On fault-tolerant path optimization under QoS constraint in multi-channel wireless networks, A linear algorithm for 2-bend embeddings of planar graphs in the two-dimensional grid, Linear area upward drawings of AVL trees, Simple undirected two-commodity integral flow with a unitary demand, Optimal node disjoint paths on partial 2-trees: A linear algorithm and polyhedral results, The directed subgraph homeomorphism problem, Linear time algorithms for two disjoint paths problems on directed acyclic graphs, Rooted \(K_4\)-minors, The disjoint shortest paths problem, The subgraph homeomorphism problem, Bonds with parity constraints, On making directed graphs transitive, A Very Practical Algorithm for the Two-Paths Problem in 3-Connected Planar Graphs, A Trichotomy for Regular Trail Queries, (Arc-)disjoint flows in networks, The complexity of routing problems in forbidden-transition graphs and edge-colored graphs, A simple solution to the two paths problem in planar graphs, Improved algorithms for finding length-bounded two vertex-disjoint paths in a planar graph and minmax \(k\) vertex-disjoint paths in a directed acyclic graph, Optimal parallel algorithms for path problems on planar graphs, Hypernetworks in a directed hypergraph, The point-to-point delivery and connection problems: Complexity and algorithms, A linear algorithm for the all-bidirectional-edges problem on planar graphs, Balanced paths in acyclic networks: Tractable cases and related approaches, Improved Algorithms for the 2-Vertex Disjoint Paths Problem, The complexity of finding two disjoint paths with min-max objective function, Disjoint paths in symmetric digraphs, Computing the rooted triplet distance between phylogenetic networks, Walking through waypoints, Strictly-upward drawings of ordered search trees, Bounds on path connectivity, Structure and recognition of graphs with no 6-wheel subdivision, Disjoint directed and undirected paths and cycles in digraphs, Advances in the theory and practice of graph drawing, Finding the k Shortest Paths, Rectilinear paths among rectilinear obstacles, The Directed Disjoint Shortest Paths Problem, Acyclic Digraphs, Displaying trees across two phylogenetic networks, 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
