Maintaining bridge-connected and biconnected components on-line

Jeffery Westbrook, Robert E. Tarjan

Research output: Contribution to journalArticle

79 Scopus citations

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(n log n +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α(m, n)), where α is a functional inverse of Ackermann's function. This time bound is optimal. All of the algorithms use O(n) space.

Original languageEnglish (US)
Pages (from-to)433-464
Number of pages32
JournalAlgorithmica
Volume7
Issue number1
DOIs
StatePublished - Dec 1 1992

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Keywords

  • Data structures
  • Dynamic trees
  • Graph algorithms
  • Graph connectivity
  • On-line algorithms

Fingerprint Dive into the research topics of 'Maintaining bridge-connected and biconnected components on-line'. Together they form a unique fingerprint.

  • Cite this