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, G. - 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.
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.
