---
_id: '11805'
abstract:
- lang: eng
  text: In this paper, we present sparse certificates for biconnectivity together
    with algorithms for updating these certificates. We thus obtain fully-dynamic
    algorithms for biconnectivity in graphs that run in O(√n log n log⌈m/n⌉) amortized
    time per operation, where m is the number of edges and n is the number of nodes
    in the graph. This improves upon the results in [11], in which algorithms were
    presented running in O(√m) amortized time, and solves the open problem to find
    certificates to speed up biconnectivity, as stated in [2].
alternative_title:
- LNCS
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: Han
  full_name: Poutré, Han
  last_name: Poutré
citation:
  ama: 'Henzinger M, Poutré H. Certificates and fast algorithms for biconnectivity
    in fully-dynamic graphs. In: <i>3rd Annual European Symposium on Algorithms</i>.
    Vol 979. Springer Nature; 1995:171–184. doi:<a href="https://doi.org/10.1007/3-540-60313-1_142">10.1007/3-540-60313-1_142</a>'
  apa: 'Henzinger, M., &#38; Poutré, H. (1995). Certificates and fast algorithms for
    biconnectivity in fully-dynamic graphs. In <i>3rd Annual European Symposium on
    Algorithms</i> (Vol. 979, pp. 171–184). Corfu, Greece: Springer Nature. <a href="https://doi.org/10.1007/3-540-60313-1_142">https://doi.org/10.1007/3-540-60313-1_142</a>'
  chicago: Henzinger, Monika, and Han Poutré. “Certificates and Fast Algorithms for
    Biconnectivity in Fully-Dynamic Graphs.” In <i>3rd Annual European Symposium on
    Algorithms</i>, 979:171–184. Springer Nature, 1995. <a href="https://doi.org/10.1007/3-540-60313-1_142">https://doi.org/10.1007/3-540-60313-1_142</a>.
  ieee: M. Henzinger and H. Poutré, “Certificates and fast algorithms for biconnectivity
    in fully-dynamic graphs,” in <i>3rd Annual European Symposium on Algorithms</i>,
    Corfu, Greece, 1995, vol. 979, pp. 171–184.
  ista: 'Henzinger M, Poutré H. 1995. Certificates and fast algorithms for biconnectivity
    in fully-dynamic graphs. 3rd Annual European Symposium on Algorithms. ESA: European
    Symposium on Algorithms, LNCS, vol. 979, 171–184.'
  mla: Henzinger, Monika, and Han Poutré. “Certificates and Fast Algorithms for Biconnectivity
    in Fully-Dynamic Graphs.” <i>3rd Annual European Symposium on Algorithms</i>,
    vol. 979, Springer Nature, 1995, pp. 171–184, doi:<a href="https://doi.org/10.1007/3-540-60313-1_142">10.1007/3-540-60313-1_142</a>.
  short: M. Henzinger, H. Poutré, in:, 3rd Annual European Symposium on Algorithms,
    Springer Nature, 1995, pp. 171–184.
conference:
  end_date: 1995-09-27
  location: Corfu, Greece
  name: 'ESA: European Symposium on Algorithms'
  start_date: 1995-09-25
date_created: 2022-08-11T14:09:52Z
date_published: 1995-09-01T00:00:00Z
date_updated: 2024-11-06T12:16:15Z
day: '01'
doi: 10.1007/3-540-60313-1_142
extern: '1'
intvolume: '       979'
language:
- iso: eng
month: '09'
oa_version: None
page: 171–184
publication: 3rd Annual European Symposium on Algorithms
publication_identifier:
  eisbn:
  - '9783540449133'
  eissn:
  - 1611-3349
  isbn:
  - '9783540603139'
  issn:
  - 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Certificates and fast algorithms for biconnectivity in fully-dynamic graphs
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 979
year: '1995'
...