TY - JOUR

T1 - Fully dynamic maintenance of k-connectivity in parallel

AU - Liang, Weifa

AU - Brent, Richard P.

AU - Shen, Hong

PY - 2001/8

Y1 - 2001/8

N2 - Given a graph G = (V, E) with n vertices and m edges, the k-connectivity of G denotes either the k-edge connectivity or the k-vertex connectivity of G. In this paper, we deal with the fully dynamic maintenance of k-connectivity of C in the parallel setting for k = 2, 3. We study the problem of maintaining k-edge/vertex connected components of a graph undergoing repeatedly dynamic updates, such as edge insertions and deletions, and answering the query of whether two vertices are included in the same k-edge/vertex connected component. Our major results are the following: 1) An NC algorithm for the 2-edge connectivity problem is proposed, which runs in O(log n log(m/n)) time using O(n 3/4) processors per update and query. 2) It is shown that the biconnectivity problem can be solved in O(log 2 n) time using O(nα(2n, n)/log n) processors per update and O(1) time with a single processor per query or in O(log n log m/n) time using O(nα(2n, n)/log n) processors per update and O(log n) time using O(nα(2n, n)/log n) processors per query, where α(., .) is the inverse of Ackermann's function. 3) An NC algorithm for the triconnectivity problem is also derived, which takes O(log n log m/n + log n loglog n/α(3n, n)) time using O(nα(3n, n)/log n) processors per update and O(1) time with a single processor per query. 4) An NC algorithm for the 3-edge connectivity problem is obtained, which has the same time and processor complexities as the algorithm for the triconnectivity problem. To the best of our knowledge, the proposed algorithms are the first NC algorithms for the problems using O(n) processors in contrast to Ω(m) processors for solving them from scratch. In particular, the proposed NC algorithm for the 2-edge connectivity problem uses only O(n 3/4)) processors. All the proposed algorithms run on a CRCW PRAM.

AB - Given a graph G = (V, E) with n vertices and m edges, the k-connectivity of G denotes either the k-edge connectivity or the k-vertex connectivity of G. In this paper, we deal with the fully dynamic maintenance of k-connectivity of C in the parallel setting for k = 2, 3. We study the problem of maintaining k-edge/vertex connected components of a graph undergoing repeatedly dynamic updates, such as edge insertions and deletions, and answering the query of whether two vertices are included in the same k-edge/vertex connected component. Our major results are the following: 1) An NC algorithm for the 2-edge connectivity problem is proposed, which runs in O(log n log(m/n)) time using O(n 3/4) processors per update and query. 2) It is shown that the biconnectivity problem can be solved in O(log 2 n) time using O(nα(2n, n)/log n) processors per update and O(1) time with a single processor per query or in O(log n log m/n) time using O(nα(2n, n)/log n) processors per update and O(log n) time using O(nα(2n, n)/log n) processors per query, where α(., .) is the inverse of Ackermann's function. 3) An NC algorithm for the triconnectivity problem is also derived, which takes O(log n log m/n + log n loglog n/α(3n, n)) time using O(nα(3n, n)/log n) processors per update and O(1) time with a single processor per query. 4) An NC algorithm for the 3-edge connectivity problem is obtained, which has the same time and processor complexities as the algorithm for the triconnectivity problem. To the best of our knowledge, the proposed algorithms are the first NC algorithms for the problems using O(n) processors in contrast to Ω(m) processors for solving them from scratch. In particular, the proposed NC algorithm for the 2-edge connectivity problem uses only O(n 3/4)) processors. All the proposed algorithms run on a CRCW PRAM.

KW - 2-edge/vertex connectivity

KW - 3-edge/vertex connectivity

KW - Dynamic data structures

KW - Graph problems

KW - NC algorithms

KW - Parallel algorithm design and analysis

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

U2 - 10.1109/71.946661

DO - 10.1109/71.946661

M3 - Article

SN - 1045-9219

VL - 12

SP - 846

EP - 864

JO - IEEE Transactions on Parallel and Distributed Systems

JF - IEEE Transactions on Parallel and Distributed Systems

IS - 8

ER -