Maintaining Bridge-Connected and Biconnected Components On-Line

Abstract

We consider the twin problems of maintaining the bridge-connected components and the biconnected components of a dynamic undirected graph. The allowed changes to the graph are vertex and edge insertions. We give an algorithm for each problem. With simple data structures, each algorithm runs in O(nlogn+m) time, where n is the number of vertices and m is the number of operations. We develop a modified version of the dynamic trees of Sleator and Tarjan that is suitable for efficient recursive algorithms, and use it to reduce the running time of the algorithms for both problems to O(m alpha(m,n), where alpha is a functional inverse of Ackermann's function. This time bound is optimal. All of the algorithms use O(n) space. (kr)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Aug 01, 1989
Accession Number
ADA215107

Entities

People

  • Jeffrey Westbrook
  • Robert Tarjan

Organizations

  • Princeton University

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Automata
  • Computer Science
  • Computers
  • Condensation
  • Digital Information
  • Distributed Computing
  • Machines
  • Mathematics
  • Models
  • New Jersey
  • Observation
  • Procedures (Computers)
  • Rotation
  • Semantic Models
  • Sequences
  • Trees (Data Structures)

Fields of Study

  • Mathematics

Readers

  • Adaptive Control and Estimation with Uncertainty in Dynamic Systems.
  • Neural Network Machine Learning.
  • Optical Fiber Sensing and Electromagnetic Propagation.

Technology Areas

  • Space