---
_id: '11684'
abstract:
- lang: eng
  text: 'This paper presents an algorithm for the fully dynamic biconnectivity problem
    whose running time is exponentially faster than all previously known solutions.
    It is the first dynamic algorithm that answers biconnectivity queries in time
    O(log/sup 2/n) in a n-node graph and can be updated after an edge insertion or
    deletion in polylogarithmic time. Our algorithm is a Las-Vegas style randomized
    algorithm with the update time amortized update time O(log/sup 4/n). Only recently
    the best deterministic result for this problem was improved to O(/spl radic/nlog/sup
    2/n). We also give the first fully dynamic and a novel deletions-only transitive
    closure (i.e. directed connectivity) algorithms. These are randomized Monte Carlo
    algorithms. Let n be the number of nodes in the graph and let m/spl circ/ be the
    average number of edges in the graph during the whole update sequence: The fully
    dynamic algorithms achieve (1) query time O(n/logn) and update time O(m/spl circ//spl
    radic/nlog/sup 2/n+n); or (2) query time O(n/logn) and update time O(nm/spl circ//sup
    /spl mu/-1/)log/sup 2/n=O(nm/spl circ//sup 0.58/log/sup 2/n), where /spl mu/ is
    the exponent for boolean matrix multiplication (currently /spl mu/=2.38). The
    deletions-only algorithm answers queries in time O(n/logn). Its amortized update
    time is O(nlog/sup 2/n).'
article_processing_charge: No
author:
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: V.
  full_name: King, V.
  last_name: King
citation:
  ama: 'Henzinger MH, King V. Fully dynamic biconnectivity and transitive closure.
    In: <i>Proceedings of IEEE 36th Annual Foundations of Computer Science</i>. Institute
    of Electrical and Electronics Engineers; 1995:664-672. doi:<a href="https://doi.org/10.1109/SFCS.1995.492668">10.1109/SFCS.1995.492668</a>'
  apa: 'Henzinger, M. H., &#38; King, V. (1995). Fully dynamic biconnectivity and
    transitive closure. In <i>Proceedings of IEEE 36th Annual Foundations of Computer
    Science</i> (pp. 664–672). Milwaukee, WI, United States: Institute of Electrical
    and Electronics Engineers. <a href="https://doi.org/10.1109/SFCS.1995.492668">https://doi.org/10.1109/SFCS.1995.492668</a>'
  chicago: Henzinger, Monika H, and V. King. “Fully Dynamic Biconnectivity and Transitive
    Closure.” In <i>Proceedings of IEEE 36th Annual Foundations of Computer Science</i>,
    664–72. Institute of Electrical and Electronics Engineers, 1995. <a href="https://doi.org/10.1109/SFCS.1995.492668">https://doi.org/10.1109/SFCS.1995.492668</a>.
  ieee: M. H. Henzinger and V. King, “Fully dynamic biconnectivity and transitive
    closure,” in <i>Proceedings of IEEE 36th Annual Foundations of Computer Science</i>,
    Milwaukee, WI, United States, 1995, pp. 664–672.
  ista: Henzinger MH, King V. 1995. Fully dynamic biconnectivity and transitive closure.
    Proceedings of IEEE 36th Annual Foundations of Computer Science. Foundations of
    Computer Science, 664–672.
  mla: Henzinger, Monika H., and V. King. “Fully Dynamic Biconnectivity and Transitive
    Closure.” <i>Proceedings of IEEE 36th Annual Foundations of Computer Science</i>,
    Institute of Electrical and Electronics Engineers, 1995, pp. 664–72, doi:<a href="https://doi.org/10.1109/SFCS.1995.492668">10.1109/SFCS.1995.492668</a>.
  short: M.H. Henzinger, V. King, in:, Proceedings of IEEE 36th Annual Foundations
    of Computer Science, Institute of Electrical and Electronics Engineers, 1995,
    pp. 664–672.
conference:
  end_date: 1995-10-25
  location: Milwaukee, WI, United States
  name: Foundations of Computer Science
  start_date: 1995-10-23
date_created: 2022-07-28T11:28:13Z
date_published: 1995-11-01T00:00:00Z
date_updated: 2023-02-09T11:35:17Z
day: '01'
doi: 10.1109/SFCS.1995.492668
extern: '1'
language:
- iso: eng
month: '11'
oa_version: None
page: 664-672
publication: Proceedings of IEEE 36th Annual Foundations of Computer Science
publication_identifier:
  isbn:
  - 0-8186-7183-1
  issn:
  - 0272-5428
publication_status: published
publisher: Institute of Electrical and Electronics Engineers
quality_controlled: '1'
scopus_import: '1'
status: public
title: Fully dynamic biconnectivity and transitive closure
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '1995'
...