TY - JOUR

T1 - Scan-first search and sparse certificates. An improved parallel algorithm for k-vertex connectivity

AU - Cheriyan, Joseph

AU - Kao, Ming Yang

AU - Thurimella, Ramakrishna

PY - 1993

Y1 - 1993

N2 - Given a graph G = (V,E), a certificate of k-vertex connectivity is an edge subset E′ ⊃ E such that the subgraph (V, E′) is k-vertex connected if and only if G is k-vertex connected. Let n and m denote the number of vertices and edges. A certificate is called sparse if it contains O(kn) edges. For undirected graphs, this paper introduces a graph search called the scan-first search, and shows that a certificate with at most k(n - 1) edges can be computed by executing scan-first search k times in sequence on subgraphs of G. For each of the parallel, distributed, and sequential models of computation, the complexity of scan-first search matches the best complexity of any graph search on that model. In particular, the parallel scan-first search runs in O(log n) time using C(n, m) processors on a CRCW PRAM, where C(n, m) is the number of processors needed to find a spanning tree in each connected component in O(log n) time, and the parallel certificate algorithm runs in O(k log n) time using C(n, m) processors. The parallel certificate algorithm can be employed to test the k-vertex connectivity of an undirected graph in O(k2 log n) time using knC(n, kn) processors on a CRCW PRAM. For all combinations of n, m, and k > 3, both the tunning time and the number of processors either improve on or match those of all known deterministic parallel algorithms. This paper also obtains an online algorithm for computing an undirected graph certificate with at most 2kn edges, and a sequential algorithm for computing a directed graph certificate with at most 2k2n edges.

AB - Given a graph G = (V,E), a certificate of k-vertex connectivity is an edge subset E′ ⊃ E such that the subgraph (V, E′) is k-vertex connected if and only if G is k-vertex connected. Let n and m denote the number of vertices and edges. A certificate is called sparse if it contains O(kn) edges. For undirected graphs, this paper introduces a graph search called the scan-first search, and shows that a certificate with at most k(n - 1) edges can be computed by executing scan-first search k times in sequence on subgraphs of G. For each of the parallel, distributed, and sequential models of computation, the complexity of scan-first search matches the best complexity of any graph search on that model. In particular, the parallel scan-first search runs in O(log n) time using C(n, m) processors on a CRCW PRAM, where C(n, m) is the number of processors needed to find a spanning tree in each connected component in O(log n) time, and the parallel certificate algorithm runs in O(k log n) time using C(n, m) processors. The parallel certificate algorithm can be employed to test the k-vertex connectivity of an undirected graph in O(k2 log n) time using knC(n, kn) processors on a CRCW PRAM. For all combinations of n, m, and k > 3, both the tunning time and the number of processors either improve on or match those of all known deterministic parallel algorithms. This paper also obtains an online algorithm for computing an undirected graph certificate with at most 2kn edges, and a sequential algorithm for computing a directed graph certificate with at most 2k2n edges.

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

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

U2 - 10.1137/0222013

DO - 10.1137/0222013

M3 - Article

AN - SCOPUS:0027544455

SN - 0097-5397

VL - 22

SP - 154

EP - 174

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 1

ER -