@conference {15199,
	title = {Efficient parallel algorithms for testing connectivity and finding disjoint s-t paths in graphs},
	booktitle = {Foundations of Computer Science, 1989., 30th Annual Symposium on},
	year = {1989},
	month = {1989/11/01/oct},
	pages = {288 - 293},
	abstract = {An efficient parallel algorithm for testing whether a graph <e1>G </e1> is <e1>K</e1>-vertex connected, for any fixed <e1>k</e1>, is presented. The algorithm runs in <e1>O</e1>(log <e1>n</e1>) time and uses <e1>nC</e1>(<e1>n</e1>,<e1>m</e1>) processors on a concurrent-read, concurrent-write parallel random-access machine (CRCW PRAM), where <e1>n </e1> and <e1>m</e1> are the number of vertices and edges of <e1>G</e1> and <e1>C</e1>(<e1>n</e1>,<e1>m</e1>) is the number of processors required to compute the connected components of <e1>G</e1> in logarithmic time. An optimal speedup algorithm for computing connected components would induce an optimal speedup algorithm for testing <e1>k </e1>-vertex connectivity, for any <e1>k</e1> gt;4. To develop the algorithm, an efficient parallel algorithm is designed for the following disjoint <e1>s</e1>-<e1>t</e1> paths problem: Given a graph <e1>G</e1> and two specified vertices <e1>s</e1> and <e1>t</e1>, find <e1>k</e1>-vertex disjoint paths between <e1>s</e1> and <e1>t</e1>, if they exist. If no such paths exist, find a set of at most <e1>k</e1>-1 vertices whose removal disconnects <e1>s</e1> and <e1>t</e1>. The parallel algorithm for this problem runs in <e1>O</e1>(log <e1>n</e1>) time using <e1>C</e1>(<e1>n</e1>,<e1>m</e1>) processors. It is shown how to modify the algorithm to find <e1>k</e1>-edge disjoint paths, if they exist. This yields an efficient parallel algorithm for testing whether a graph <e1>G</e1> is <e1>k</e1>-edge connected, for any fixed <e1>k</e1>. The algorithm runs in <e1>O</e1>(log <e1>n</e1>) time and uses <e1>nC </e1> (<e1>n</e1>,<e1>n</e1>) processors on a CRCW PRAM. Again, an optimal speedup algorithm for computing connected components would induce an optimal speedup algorithm for testing <e1>k</e1>-edge connectivity},
	keywords = {algorithm;parallel, algorithms;random-access, algorithms;testing, complexity;graph, connectivity;computational, connectivity;optimal, CRCW, disjoint, paths;graphs;k-edge, paths;k-vertex, PRAM;disjoint, s-t, speedup, storage;, theory;parallel},
	doi = {10.1109/SFCS.1989.63492},
	author = {Khuller, Samir and Schieber,B.}
}
