Fully dynamic maintaining 2-edge connectivity in parallel

Weifa Liang, Hong Shen

Research output: Contribution to journalConference articlepeer-review

1 Citation (Scopus)


This paper studies the problem of maintaining the 2-edge-connected components of a graph undergoing repeatedly dynamic updates such as edge insertions and deletions. It is shown that all operations such as inserting an edge to or deleting an edge from the graph, and answering the query about whether two vertices belong to the same 2-edge connected component can be completed in O(log m) time with O(m 3/4) processors or in O(log n log(m/n)) time with O(n 3/4) processors on a priority CRCW PRAM, where m is the current number of edges and n is the number of vertices. To our knowledge, the proposed algorithm is the first NC algorithm for this problem using sublinear number processors o(m).

Original languageEnglish
Pages (from-to)216-223
Number of pages8
JournalIEEE Symposium on Parallel and Distributed Processing - Proceedings
Publication statusPublished - 1995
Externally publishedYes
EventProceedings of the 1995 7th IEEE Symposium on Parallel and Distributed Processing - San Antonio, TX, USA
Duration: 25 Oct 199528 Oct 1995


Dive into the research topics of 'Fully dynamic maintaining 2-edge connectivity in parallel'. Together they form a unique fingerprint.

Cite this