TY - JOUR

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

AU - Khuller, Samir

AU - Schieber, Baruch

PY - 1991/1/1

Y1 - 1991/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0026138636&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0026138636&partnerID=8YFLogxK

U2 - 10.1137/0220022

DO - 10.1137/0220022

M3 - Article

AN - SCOPUS:0026138636

VL - 20

SP - 352

EP - 375

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

SN - 0097-5397

IS - 2

ER -