Decremental 2- and 3-connectivity on planar graphs |
| |
Authors: | D Giammarresi G F Italiano |
| |
Affiliation: | (1) Dipartimento di Matematica e Applicazioni, Università di Palermo, Italy;(2) Dipartimento di Informatica e Sistemistica, Università di Roma La Sapienza,, Italy |
| |
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 ofO(n logn) time under any sequence of at mostO(n) deletions. This givesO(logn) amortized time per deletion. The 2-vertex- and 3-edge-connected components can be maintained in a total ofO(n log2
n) time. This givesO(log2
n) amortized time per deletion. The space required by all our data structures isO(n). All our time bounds improve previous bounds.This work was partially supported by the ESPRIT II Basic Research Actions Program of the EC under Project ALCOM II (contract No. 7141) and Project ASMICS. A preliminary version of this paper appears in 12].Partially supported by a CNR Fellowship. Work done while the author was visiting Columbia University.On leave from IBM T. J. Watson Research Center, Yorktown Heights, NY 10598, USA. |
| |
Keywords: | Analysis of algorithms Dynamic data structures Edge connectivity Planar graphs Vertex connectivity |
本文献已被 SpringerLink 等数据库收录! |
|