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.

Fully dynamic algorithms for 2-edge connectivity / Galil, Z; Italiano, G. - In: SIAM JOURNAL ON COMPUTING. - ISSN 0097-5397. - 21:6(1992), pp. 1047-1069. [10.1137/0221062]

Fully dynamic algorithms for 2-edge connectivity

Italiano G
1992

Abstract

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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11385/191468
Citazioni
  • Scopus ND
  • ???jsp.display-item.citation.isi??? 13
social impact