This paper studies the problem of maintaining the 2-edge-connected components of a graph undergoing repeated dynamic modifications, such as edge insertions and edge deletions. It is shown how to test at any time whether two vertices belong to the same 2-edge-connected component, and how to insert and delete an edge in $O(m^{2/3} )$ time in the worst case, where m is the current number of edges in the graph.
Titolo: | Fully dynamic algorithms for 2-edge connectivity |
Autori: | |
Data di pubblicazione: | 1992 |
Rivista: | |
Handle: | http://hdl.handle.net/11385/191468 |
Appare nelle tipologie: | 01.1 - Articolo su rivista (Article) |
File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.