Improved data structures for fully dynamic biconnectivity

Monika Rauch

1994 · 40 citations · 22 references

DOIFull text

Open access

Concepts

Abstract

We present fully dynamic algorithms for maintaining the biconnected components in general and plane graphs and lower bounds for fully dynamic k-edge connectivity, k-vertex connectivity, and planarity testing. Fully dynamic algorithms maintain a graph during a sequence of insertions and deletions of edges or isolated vertices. Let m be the number of edges and n be the number of vertices in a graph. The time per operation of the best known algorithms are 0(@) in general graphs and O(log n) in plane graphs for fully dynamic connectivity and O(min{m2/3, n}) in general graphs and O(@)

References

22