%0 Conference Paper
%B Foundations of Computer Science, 1989., 30th Annual Symposium on
%D 1989
%T Efficient parallel algorithms for testing connectivity and finding disjoint s-t paths in graphs
%A Khuller, Samir
%A Schieber,B.
%K algorithm;parallel
%K algorithms;random-access
%K algorithms;testing
%K complexity;graph
%K connectivity;computational
%K connectivity;optimal
%K CRCW
%K disjoint
%K paths;graphs;k-edge
%K paths;k-vertex
%K PRAM;disjoint
%K s-t
%K speedup
%K storage;
%K theory;parallel
%X 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
%B Foundations of Computer Science, 1989., 30th Annual Symposium on
%P 288 - 293
%8 1989/11/01/oct
%G eng
%R 10.1109/SFCS.1989.63492