---
_id: '4612'
alternative_title:
- LNCS
article_processing_charge: No
citation:
  ama: 'Alur R, Henzinger TA, Sontag ED, eds. <i>Hybrid Systems III: Verification
    and Control</i>. Vol 1066. Berlin ; Heidelberg: Springer; 1996. doi:<a href="https://doi.org/10.1007/BFb0020931">10.1007/BFb0020931</a>'
  apa: 'Alur, R., Henzinger, T. A., &#38; Sontag, E. D. (Eds.). (1996). <i>Hybrid
    Systems III: Verification and Control</i> (Vol. 1066). Berlin ; Heidelberg: Springer.
    <a href="https://doi.org/10.1007/BFb0020931">https://doi.org/10.1007/BFb0020931</a>'
  chicago: 'Alur, Rajeev, Thomas A Henzinger, and Eduardo D Sontag, eds. <i>Hybrid
    Systems III: Verification and Control</i>. Vol. 1066. Lecture Notes in Computer
    Science. Berlin ; Heidelberg: Springer, 1996. <a href="https://doi.org/10.1007/BFb0020931">https://doi.org/10.1007/BFb0020931</a>.'
  ieee: 'R. Alur, T. A. Henzinger, and E. D. Sontag, Eds., <i>Hybrid Systems III:
    Verification and Control</i>, vol. 1066. Berlin ; Heidelberg: Springer, 1996.'
  ista: 'Alur R, Henzinger TA, Sontag ED eds. 1996. Hybrid Systems III: Verification
    and Control, Berlin ; Heidelberg: Springer, IX, 619p.'
  mla: 'Alur, Rajeev, et al., editors. <i>Hybrid Systems III: Verification and Control</i>.
    Vol. 1066, Springer, 1996, doi:<a href="https://doi.org/10.1007/BFb0020931">10.1007/BFb0020931</a>.'
  short: 'R. Alur, T.A. Henzinger, E.D. Sontag, eds., Hybrid Systems III: Verification
    and Control, Springer, Berlin ; Heidelberg, 1996.'
date_created: 2018-12-11T12:09:45Z
date_published: 1996-01-01T00:00:00Z
date_updated: 2021-12-22T13:57:33Z
day: '01'
doi: 10.1007/BFb0020931
editor:
- first_name: Rajeev
  full_name: Alur, Rajeev
  last_name: Alur
- first_name: Thomas A
  full_name: Henzinger, Thomas A
  id: 40876CD8-F248-11E8-B48F-1D18A9856A87
  last_name: Henzinger
  orcid: 0000−0002−2985−7724
- first_name: Eduardo D
  full_name: Sontag, Eduardo D
  last_name: Sontag
extern: '1'
intvolume: '      1066'
language:
- iso: eng
month: '01'
oa_version: None
page: IX, 619
place: Berlin ; Heidelberg
publication_identifier:
  isbn:
  - 978-3-540-61155-4
  issn:
  - 0302-9743
publication_status: published
publisher: Springer
publist_id: '97'
quality_controlled: '1'
series_title: Lecture Notes in Computer Science
status: public
title: 'Hybrid Systems III: Verification and Control'
type: book_editor
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
volume: 1066
year: '1996'
...
---
_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'
...
---
_id: '11806'
abstract:
- lang: eng
  text: This paper presents insertions-only algorithms for maintaining the exact and
    approximate size of the minimum edge cut and the minimum vertex cut of a graph.
    The algorithms output the approximate or exact size k in time O(1) or O(log n)
    and a cut of size k in time linear in its size. The amortized time per insertion
    is O(1/ε 2) for a (2+ε)-approximation, O((log λ)((log n)/ε)2) for a (1+ε)-approximation,
    and O(λ log n) for the exact size of the minimum edge cut, where n is the number
    of nodes in the graph, λ is the size of the minimum cut and ε>0. The (2+ε)-approximation
    algorithm and the exact algorithm are deterministic, the (1+ε)-approximation algorithm
    is randomized. The algorithms are optimal in the sense that the time needed for
    m insertions matches the time needed by the best static algorithm on a m-edge
    graph. We also present a static 2-approximation algorithm for the size κ of the
    minimum vertex cut in a graph, which takes time O(n 2 min(√n,κ)). This is a factor
    of κ faster than the best algorithm for computing the exact size, which takes
    time O(κ 2 n 2 +κ 3 n 1.5). We give an insertionsonly algorithm for maintaining
    a (2+ε)-approximation of the minimum vertex cut with amortized insertion time
    O(n(logκk)/ε).
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
citation:
  ama: 'Henzinger M. Approximating minimum cuts under insertions. In: <i>22nd International
    Colloquium on Automata, Languages and Programming</i>. Vol 944. Springer Nature;
    1995:280–291. doi:<a href="https://doi.org/10.1007/3-540-60084-1_81">10.1007/3-540-60084-1_81</a>'
  apa: 'Henzinger, M. (1995). Approximating minimum cuts under insertions. In <i>22nd
    International Colloquium on Automata, Languages and Programming</i> (Vol. 944,
    pp. 280–291). Szeged, Hungary: Springer Nature. <a href="https://doi.org/10.1007/3-540-60084-1_81">https://doi.org/10.1007/3-540-60084-1_81</a>'
  chicago: Henzinger, Monika. “Approximating Minimum Cuts under Insertions.” In <i>22nd
    International Colloquium on Automata, Languages and Programming</i>, 944:280–291.
    Springer Nature, 1995. <a href="https://doi.org/10.1007/3-540-60084-1_81">https://doi.org/10.1007/3-540-60084-1_81</a>.
  ieee: M. Henzinger, “Approximating minimum cuts under insertions,” in <i>22nd International
    Colloquium on Automata, Languages and Programming</i>, Szeged, Hungary, 1995,
    vol. 944, pp. 280–291.
  ista: 'Henzinger M. 1995. Approximating minimum cuts under insertions. 22nd International
    Colloquium on Automata, Languages and Programming. ICALP: International Colloquium
    on Automata, Languages, and Programming, LNCS, vol. 944, 280–291.'
  mla: Henzinger, Monika. “Approximating Minimum Cuts under Insertions.” <i>22nd International
    Colloquium on Automata, Languages and Programming</i>, vol. 944, Springer Nature,
    1995, pp. 280–291, doi:<a href="https://doi.org/10.1007/3-540-60084-1_81">10.1007/3-540-60084-1_81</a>.
  short: M. Henzinger, in:, 22nd International Colloquium on Automata, Languages and
    Programming, Springer Nature, 1995, pp. 280–291.
conference:
  end_date: 1995-07-14
  location: Szeged, Hungary
  name: 'ICALP: International Colloquium on Automata, Languages, and Programming'
  start_date: 1995-07-10
date_created: 2022-08-11T14:17:33Z
date_published: 1995-07-01T00:00:00Z
date_updated: 2024-11-06T08:23:27Z
day: '01'
doi: 10.1007/3-540-60084-1_81
extern: '1'
intvolume: '       944'
language:
- iso: eng
month: '07'
oa_version: None
page: 280–291
publication: 22nd International Colloquium on Automata, Languages and Programming
publication_identifier:
  eisbn:
  - '9783540600848'
  eissn:
  - 1611-3349
  isbn:
  - '9783540494256'
  issn:
  - 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Approximating minimum cuts under insertions
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 944
year: '1995'
...