Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell Computing and Information Science
  3. Computer Science
  4. Computer Science Technical Reports
  5. Improved Data Structures for Fully Dynamic Biconnectivity

Improved Data Structures for Fully Dynamic Biconnectivity

File(s)
94-1412.pdf (3.64 MB)
94-1412.ps (446.84 KB)
Permanent Link(s)
https://hdl.handle.net/1813/6194
Collections
Computer Science Technical Reports
Author
Rauch, Monika H.
Abstract

We present fully dynamic algorithms for maintaining the biconnected components in general and plane graphs. A fully dynamic algorithm maintains a graph during a sequence of insertions and 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 $O(\sqrt{n})$ in general graphs and $O(\log n)$ in plane graphs for fully dynamic connectivity and $O(\min{m^{2/3}, n})$ in general graphs and $O(\sqrt{n})$ in plane graphs for fully dynamic biconnectivity. We improve the later running times to $(\min{\sqrt{m}\log n, n })$ in general graphs and $O(\log^{2}n)$ in plane graphs. Our algorithm for general graphs can also find the biconnected components of all vertices in time $O(n)$. The update times in general graphs are amortized. This shows that the biconnected components of a graph can be dynamically maintained almost as efficiently as the connected components.

Date Issued
1994-02
Publisher
Cornell University
Keywords
computer science
•
technical report
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR94-1412
Type
technical report

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance