We study the problem of maintaining the 2-edge-, 2-vertex-, and 3-edge-connected components of a dynamic planar graph subject to edge deletions. The 2-edge-connected components can be maintained in a total of O(n logn) time under any sequence of at most O(n) deletions. This gives O(logn) amortized time per deletion. The 2-vertex- and 3-edge-connected components can be maintained in a total of O (n log 2 n) time. This gives O(log 2 n) amortized time per deletion. The space required by all our data structures is O(n). All our time bounds improve previous bounds.

Decremental 2- and 3-connectivity on planar graphs / Giammarresi, D.; Italiano, Giuseppe Francesco. - In: ALGORITHMICA. - ISSN 0178-4617. - 16:3(1996), pp. 263-287.

Decremental 2- and 3-connectivity on planar graphs

Italiano G
1996

Abstract

We study the problem of maintaining the 2-edge-, 2-vertex-, and 3-edge-connected components of a dynamic planar graph subject to edge deletions. The 2-edge-connected components can be maintained in a total of O(n logn) time under any sequence of at most O(n) deletions. This gives O(logn) amortized time per deletion. The 2-vertex- and 3-edge-connected components can be maintained in a total of O (n log 2 n) time. This gives O(log 2 n) amortized time per deletion. The space required by all our data structures is O(n). All our time bounds improve previous bounds.
Analysis of algorithms, Dynamic data structures, Edge connectivity, Planar graphs, Vertex connectivity
Decremental 2- and 3-connectivity on planar graphs / Giammarresi, D.; Italiano, Giuseppe Francesco. - In: ALGORITHMICA. - ISSN 0178-4617. - 16:3(1996), pp. 263-287.
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/199841
Citazioni
  • Scopus 9
  • ???jsp.display-item.citation.isi??? 6
social impact