Abstract
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 language | English |
|---|---|
| Pages (from-to) | 216-223 |
| Number of pages | 8 |
| Journal | IEEE Symposium on Parallel and Distributed Processing - Proceedings |
| Publication status | Published - 1995 |
| Externally published | Yes |
| Event | Proceedings of the 1995 7th IEEE Symposium on Parallel and Distributed Processing - San Antonio, TX, USA Duration: 25 Oct 1995 → 28 Oct 1995 |