Fully dynamic biconnectivity in graphs |
| |
Authors: | M. R. Henzinger |
| |
Affiliation: | (1) Department of Computer Science, Cornell University, 14853 Ithaca, NY, USA |
| |
Abstract: | We present an algorithm for maintaining the biconnected components of a graph during a sequence of edge insertions and deletions. It requires linear storage and preprocessing time. The amortized running time for insertions and for deletions isO(m 2/3 ), wherem is the number of edges in the graph. Any query of the form ‘Are the verticesu andv biconnected?’ can be answered in timeO(1). This is the first sublinear algorithm for this problem. We can also output all articulation points separating any two vertices efficiently. If the input is a plane graph, the amortized running time for insertions and deletions drops toO(√n logn) and the query time isO(log2 n), wheren is the number of vertices in the graph. The best previously known solution takes timeO(n 2/3 ) per update or query. |
| |
Keywords: | Graph algorithms Dynamic algorithms Data structures Graph connectivity |
本文献已被 SpringerLink 等数据库收录! |
|