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

Samir Khuller, Baruch Schieber

Research output: Chapter in Book/Report/Conference proceedingConference contribution

16 Scopus citations

Abstract

An efficient parallel algorithm for testing whether a graph G is k-vertex connected, for any fixed k, is presented. The algorithm runs in O(log n) time and uses nC(n, m) processors on a concurrent-read, concurrent-write parallel random-access machine (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. An optimal speedup algorithm for computing connected components would induce an optimal speedup algorithm for testing k-vertex connectivity, for any k > 4. To develop the 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(log n) time using C(n, m) processors. It is shown how to modify the algorithm to find k-edge disjoint paths, if they exist. This yields an efficient parallel algorithm for testing whether a graph G is k-edge connected, for any fixed k. The algorithm runs in O(log n) time and uses nC (n, n) processors on a CRCW PRAM. Again, an optimal speedup algorithm for computing connected components would induce an optimal speedup algorithm for testing k-edge connectivity. Further applications of the disjoint s-t paths algorithm are described.

Original languageEnglish (US)
Title of host publicationAnnual Symposium on Foundations of Computer Science (Proceedings)
PublisherPubl by IEEE
Pages288-293
Number of pages6
ISBN (Print)0818619821
StatePublished - Nov 1 1989
Externally publishedYes
Event30th Annual Symposium on Foundations of Computer Science - Research Triangle Park, NC, USA
Duration: Oct 30 1989Nov 1 1989

Publication series

NameAnnual Symposium on Foundations of Computer Science (Proceedings)
ISSN (Print)0272-5428

Conference

Conference30th Annual Symposium on Foundations of Computer Science
CityResearch Triangle Park, NC, USA
Period10/30/8911/1/89

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

Fingerprint

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

Cite this