Abstract
Gwen a graph G = (V, E) and four verttces s1, t2, s2, and t2, the problem of finding two disjoint paths, P1 from s2 to t2 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.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 1-9 |
| Number of pages | 9 |
| Journal | Journal of the ACM (JACM) |
| Volume | 25 |
| Issue number | 1 |
| DOIs | |
| State | Published - Jan 1 1978 |
| Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Software
- Control and Systems Engineering
- Information Systems
- Hardware and Architecture
- Artificial Intelligence
Keywords
- acychc directed graphs
- chordal graphs
- connectivtty
- disjoint paths
- efficiency of algorithms
- graph algorithms
- networks
- pairs of vertices
- planar graphs
- polynomial reductions
- routing
- transportation