Finding Two Disjoint Paths Between Two Pairs of Vertices in a Graph
- 1 January 1978
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 25 (1) , 1-9
- https://doi.org/10.1145/322047.322048
Abstract
^SSTnXcr. Gwen a graph G = (V, E) and four verttces s~, tx, s~, and t2, the problem of finding two disjoint paths, P~ from s~ to tt and P2 from s2 to t2, is considered This problem may arise as a transportation network problem and m printed clrcmts routing The relations between several vemons of the problem are discussed Efficient algorithms are gwen for the following special cases-acyche directed graphs and 3-connected planar and chordal graphs.Keywords
This publication has 5 references indexed in Scilit:
- On the Complexity of Timetable and Multicommodity Flow ProblemsSIAM Journal on Computing, 1976
- Efficient Planarity TestingJournal of the ACM, 1974
- Dividing a Graph into Triconnected ComponentsSIAM Journal on Computing, 1973
- On the Existence of Certain Configurations within Graphs and the 1-Skeletons of PolytopesProceedings of the London Mathematical Society, 1970
- On the existence of certain disjoint arcs in graphsDuke Mathematical Journal, 1968