Dynamic maintenance of k-connectivity

204. W. Liang, R. P. Brent and H. Shen, Fully dynamic maintenance of k-connectivity in parallel, IEEE Transactions on Parallel and Distributed Systems 12 (2001), 846-864.

Preprint: ps (184K).

Paper: pdf (647K).


We study parallel algorithms for the problem of maintaining k-edge/vertex connected components of a graph which is undergoing repeated dynamic updates such as edge insertions and/or deletions.

[For a longer abstract, see the paper.]

Go to next publication

Return to Richard Brent's index page