Efficient parallel algorithms for testing k-connectivity and finding disjoint s-t paths in graphs

Samir Khuller*, Baruch Schieber

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

17 Scopus citations

Abstract

An efficient parallel algorithm for testing whether a graph G is k-vertex connected is presented. The algorithm runs in O(k2 log n) time and uses (n + k2) kC (n, m) processors on a CRCW PRAM, where n and m are the number of vertices and edges of G, and C(n, m) is the number of processors required to compute the connected components of G in logarithmic time. For fixed k, the algorithm runs in logarithmic time and uses nC(n, m) processors. To develop our algorithm, an efficient parallel algorithm is designed for the following disjoint s-t paths problem. Given a graph G, and two specified vertices s and t, find k vertex disjoint paths between s and t, if they exist. If no such paths exist, find a set of at most k - 1 vertices whose removal disconnects s and t. The parallel algorithm for this problem runs in O(k2 log n) time and uses kC(n, m) processors. The way to modify the algorithm to find k-edge disjoint paths, if they exist, is shown. This yields an efficient parallel algorithm for testing whether a graph G is k-edge connected. The algorithm runs in O(k2 log n) time and uses nkC(n, kn) processors on a CRCW PRAM. Finally, more applications of the disjoint s-t paths algorithm are described.

Original languageEnglish (US)
Pages (from-to)352-375
Number of pages24
JournalSIAM Journal on Computing
Volume20
Issue number2
DOIs
StatePublished - Jan 1 1991

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Efficient parallel algorithms for testing k-connectivity and finding disjoint s-t paths in graphs'. Together they form a unique fingerprint.

Cite this