The problem of maintaining the 3-edge-connected components of a graph undergoing repeated dynamic modifications, such as edge and vertex insertions, is studied. This paper shows how to answer the question of whether or not two vertices belong to the same 3-edge-connected component of a connected graph that is undergoing only edge insertions. Any sequence of q query and updates on an n-vertex graph can be performed in $O((n + q)alpha (q,n))$ time.

Maintaining the 3-edge-connected components of a graph on-line / Galil, Z.; Italiano, Giuseppe Francesco. - In: SIAM JOURNAL ON COMPUTING. - ISSN 0097-5397. - 22:1(1993), pp. 11-28. [10.1137/0222002]

Maintaining the 3-edge-connected components of a graph on-line

ITALIANO G
1993

Abstract

The problem of maintaining the 3-edge-connected components of a graph undergoing repeated dynamic modifications, such as edge and vertex insertions, is studied. This paper shows how to answer the question of whether or not two vertices belong to the same 3-edge-connected component of a connected graph that is undergoing only edge insertions. Any sequence of q query and updates on an n-vertex graph can be performed in $O((n + q)alpha (q,n))$ time.
1993
Maintaining the 3-edge-connected components of a graph on-line / Galil, Z.; Italiano, Giuseppe Francesco. - In: SIAM JOURNAL ON COMPUTING. - ISSN 0097-5397. - 22:1(1993), pp. 11-28. [10.1137/0222002]
File in questo prodotto:
Non ci sono file associati a questo prodotto.
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: https://hdl.handle.net/11385/199847
Citazioni
  • Scopus 35
  • ???jsp.display-item.citation.isi??? 25
  • OpenAlex ND
social impact