Finding Two Disjoint Paths Between Two Pairs of Vertices in a Graph

Y. Shiloach, Y. Perl

Research output: Contribution to journalArticlepeer-review

109 Scopus citations

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 languageEnglish (US)
Pages (from-to)1-9
Number of pages9
JournalJournal of the ACM (JACM)
Volume25
Issue number1
DOIs
StatePublished - Jan 1 1978
Externally publishedYes

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

Fingerprint

Dive into the research topics of 'Finding Two Disjoint Paths Between Two Pairs of Vertices in a Graph'. Together they form a unique fingerprint.

Cite this