eCommons

 

Improved Data Structures for Fully Dynamic Biconnectivity

Other Titles

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(n) in general graphs and O(logn) in plane graphs for fully dynamic connectivity and O(min{m2/3,n}) in general graphs and O(n) in plane graphs for fully dynamic biconnectivity. We improve the later running times to (min{mlogn,n}) in general graphs and O(log2n) 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.

Journal / Series

Volume & Issue

Description

Sponsorship

Date Issued

1994-02

Publisher

Cornell University

Keywords

computer science; technical report

Location

Effective Date

Expiration Date

Sector

Employer

Union

Union Local

NAICS

Number of Workers

Committee Chair

Committee Co-Chair

Committee Member

Degree Discipline

Degree Name

Degree Level

Related Version

Related DOI

Related To

Related Part

Based on Related Item

Has Other Format(s)

Part of Related Item

Related To

Related Publication(s)

Link(s) to Related Publication(s)

References

Link(s) to Reference(s)

Previously Published As

http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR94-1412

Government Document

ISBN

ISMN

ISSN

Other Identifiers

Rights

Rights URI

Types

technical report

Accessibility Feature

Accessibility Hazard

Accessibility Summary

Link(s) to Catalog Record