TY - CONF
T1 - Efficient parallel algorithms for testing connectivity and finding disjoint s-t paths in graphs
T2 - Foundations of Computer Science, 1989., 30th Annual Symposium on
Y1 - 1989
A1 - Khuller, Samir
A1 - Schieber,B.
KW - algorithm;parallel
KW - algorithms;random-access
KW - algorithms;testing
KW - complexity;graph
KW - connectivity;computational
KW - connectivity;optimal
KW - CRCW
KW - disjoint
KW - paths;graphs;k-edge
KW - paths;k-vertex
KW - PRAM;disjoint
KW - s-t
KW - speedup
KW - storage;
KW - theory;parallel
AB - 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 gt;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
JA - Foundations of Computer Science, 1989., 30th Annual Symposium on
M3 - 10.1109/SFCS.1989.63492
ER -