---
_id: '11677'
abstract:
- lang: eng
text: "We present an algorithm for maintaining the biconnected components of a graph
during a sequence of edge insertions and deletions. It requires linear storage
and preprocessing time. The amortized running time for insertions and for deletions
isO(m 2/3 ), wherem is the number of edges in the graph. Any query of the form
‘Are the verticesu andv biconnected?’ can be answered in timeO(1). This is the
first sublinear algorithm for this problem. We can also output all articulation
points separating any two vertices efficiently.\r\n\r\nIf the input is a plane
graph, the amortized running time for insertions and deletions drops toO(√n logn)
and the query time isO(log2 n), wheren is the number of vertices in the graph.
The best previously known solution takes timeO(n 2/3 ) per update or query."
article_processing_charge: No
article_type: original
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 MH. Fully dynamic biconnectivity in graphs. Algorithmica.
1995;13(6):503-538. doi:10.1007/bf01189067
apa: Henzinger, M. H. (1995). Fully dynamic biconnectivity in graphs. Algorithmica.
Springer Nature. https://doi.org/10.1007/bf01189067
chicago: Henzinger, Monika H. “Fully Dynamic Biconnectivity in Graphs.” Algorithmica.
Springer Nature, 1995. https://doi.org/10.1007/bf01189067.
ieee: M. H. Henzinger, “Fully dynamic biconnectivity in graphs,” Algorithmica,
vol. 13, no. 6. Springer Nature, pp. 503–538, 1995.
ista: Henzinger MH. 1995. Fully dynamic biconnectivity in graphs. Algorithmica.
13(6), 503–538.
mla: Henzinger, Monika H. “Fully Dynamic Biconnectivity in Graphs.” Algorithmica,
vol. 13, no. 6, Springer Nature, 1995, pp. 503–38, doi:10.1007/bf01189067.
short: M.H. Henzinger, Algorithmica 13 (1995) 503–538.
date_created: 2022-07-27T14:50:46Z
date_published: 1995-06-01T00:00:00Z
date_updated: 2022-09-12T09:00:14Z
day: '01'
doi: 10.1007/bf01189067
extern: '1'
intvolume: ' 13'
issue: '6'
language:
- iso: eng
month: '06'
oa_version: None
page: 503-538
publication: Algorithmica
publication_identifier:
eissn:
- 1432-0541
issn:
- 0178-4617
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Fully dynamic biconnectivity in graphs
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 13
year: '1995'
...
---
_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: Proceedings of IEEE 36th Annual Foundations of Computer Science. Institute
of Electrical and Electronics Engineers; 1995:664-672. doi:10.1109/SFCS.1995.492668'
apa: 'Henzinger, M. H., & King, V. (1995). Fully dynamic biconnectivity and
transitive closure. In Proceedings of IEEE 36th Annual Foundations of Computer
Science (pp. 664–672). Milwaukee, WI, United States: Institute of Electrical
and Electronics Engineers. https://doi.org/10.1109/SFCS.1995.492668'
chicago: Henzinger, Monika H, and V. King. “Fully Dynamic Biconnectivity and Transitive
Closure.” In Proceedings of IEEE 36th Annual Foundations of Computer Science,
664–72. Institute of Electrical and Electronics Engineers, 1995. https://doi.org/10.1109/SFCS.1995.492668.
ieee: M. H. Henzinger and V. King, “Fully dynamic biconnectivity and transitive
closure,” in Proceedings of IEEE 36th Annual Foundations of Computer Science,
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.” Proceedings of IEEE 36th Annual Foundations of Computer Science,
Institute of Electrical and Electronics Engineers, 1995, pp. 664–72, doi:10.1109/SFCS.1995.492668.
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'
...
---
_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 MH. Approximating minimum cuts under insertions. In: 22nd International
Colloquium on Automata, Languages and Programming. Vol 944. Springer Nature;
1995:280–291. doi:10.1007/3-540-60084-1_81'
apa: 'Henzinger, M. H. (1995). Approximating minimum cuts under insertions. In 22nd
International Colloquium on Automata, Languages and Programming (Vol. 944,
pp. 280–291). Szeged, Hungary: Springer Nature. https://doi.org/10.1007/3-540-60084-1_81'
chicago: Henzinger, Monika H. “Approximating Minimum Cuts under Insertions.” In
22nd International Colloquium on Automata, Languages and Programming, 944:280–291.
Springer Nature, 1995. https://doi.org/10.1007/3-540-60084-1_81.
ieee: M. H. Henzinger, “Approximating minimum cuts under insertions,” in 22nd
International Colloquium on Automata, Languages and Programming, Szeged, Hungary,
1995, vol. 944, pp. 280–291.
ista: 'Henzinger MH. 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 H. “Approximating Minimum Cuts under Insertions.” 22nd
International Colloquium on Automata, Languages and Programming, vol. 944,
Springer Nature, 1995, pp. 280–291, doi:10.1007/3-540-60084-1_81.
short: M.H. 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: 2023-02-14T08:09:08Z
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'
...
---
_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 MH, Poutré H. Certificates and fast algorithms for biconnectivity
in fully-dynamic graphs. In: 3rd Annual European Symposium on Algorithms.
Vol 979. Springer Nature; 1995:171–184. doi:10.1007/3-540-60313-1_142'
apa: 'Henzinger, M. H., & Poutré, H. (1995). Certificates and fast algorithms
for biconnectivity in fully-dynamic graphs. In 3rd Annual European Symposium
on Algorithms (Vol. 979, pp. 171–184). Corfu, Greece: Springer Nature. https://doi.org/10.1007/3-540-60313-1_142'
chicago: Henzinger, Monika H, and Han Poutré. “Certificates and Fast Algorithms
for Biconnectivity in Fully-Dynamic Graphs.” In 3rd Annual European Symposium
on Algorithms, 979:171–184. Springer Nature, 1995. https://doi.org/10.1007/3-540-60313-1_142.
ieee: M. H. Henzinger and H. Poutré, “Certificates and fast algorithms for biconnectivity
in fully-dynamic graphs,” in 3rd Annual European Symposium on Algorithms,
Corfu, Greece, 1995, vol. 979, pp. 171–184.
ista: 'Henzinger MH, 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 H., and Han Poutré. “Certificates and Fast Algorithms for
Biconnectivity in Fully-Dynamic Graphs.” 3rd Annual European Symposium on Algorithms,
vol. 979, Springer Nature, 1995, pp. 171–184, doi:10.1007/3-540-60313-1_142.
short: M.H. 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: 2023-02-14T08:02:03Z
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: '11928'
abstract:
- lang: eng
text: "We present a model with restricted randomness for edge updates in dynamic
graph algorithms and a general technique\r\nfor analyzing the expected running
time of an update operation. This model is able to capture the average case in
many applications, since (1) it allows restrictions on the set of edges which
can be used for insertions and (2) the type (insertion or deletion) of each update
operation is arbitrary, i.e., not random. We use our technique to analyze existing
and new dynamic algorithms for maximum cardinality matching, minimum spanning
forest, connectivity, 2-edge connectivity,\r\nk-edge connectivity, k-vertex connectivity,
and bipartiteness. Given a random graph G with mo edges and n vertices and\r\na
sequence of 1 update operations such that the graph contains rni edges after operation
i, the expected time for performing the updates for any 1 is O(1 logn + n xi=,
l/fii) in the case of minimum spanning forests, connectivity, 2-\r\nedge connectivity,
and bipartiteness. The expected time per update operation is O(n) in the case
of maximum matching. For k-edge and k-vertex connectivity we also give improved
bounds. Additionally we give an insertions-only algorithm for maximum cardinality
matching with worst-case O(n) amortized time per insertion. "
article_processing_charge: No
author:
- first_name: David
full_name: Alberts, David
last_name: Alberts
- 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: 'Alberts D, Henzinger MH. Average case analysis of dynamic graph algorithms.
In: 6th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial
and Applied Mathematics; 1995:312-321.'
apa: 'Alberts, D., & Henzinger, M. H. (1995). Average case analysis of dynamic
graph algorithms. In 6th Annual ACM-SIAM Symposium on Discrete Algorithms
(pp. 312–321). San Francisco, CA, United States: Society for Industrial and Applied
Mathematics.'
chicago: Alberts, David, and Monika H Henzinger. “Average Case Analysis of Dynamic
Graph Algorithms.” In 6th Annual ACM-SIAM Symposium on Discrete Algorithms,
312–21. Society for Industrial and Applied Mathematics, 1995.
ieee: D. Alberts and M. H. Henzinger, “Average case analysis of dynamic graph algorithms,”
in 6th Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco,
CA, United States, 1995, pp. 312–321.
ista: 'Alberts D, Henzinger MH. 1995. Average case analysis of dynamic graph algorithms.
6th Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete
Algorithms, 312–321.'
mla: Alberts, David, and Monika H. Henzinger. “Average Case Analysis of Dynamic
Graph Algorithms.” 6th Annual ACM-SIAM Symposium on Discrete Algorithms,
Society for Industrial and Applied Mathematics, 1995, pp. 312–21.
short: D. Alberts, M.H. Henzinger, in:, 6th Annual ACM-SIAM Symposium on Discrete
Algorithms, Society for Industrial and Applied Mathematics, 1995, pp. 312–321.
conference:
end_date: 1995-01-24
location: San Francisco, CA, United States
name: 'SODA: Symposium on Discrete Algorithms'
start_date: 1995-01-22
date_created: 2022-08-19T07:10:23Z
date_published: 1995-01-01T00:00:00Z
date_updated: 2023-02-21T16:24:58Z
day: '01'
extern: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://dl.acm.org/doi/10.5555/313651.313712
month: '01'
oa: 1
oa_version: Published Version
page: 312-321
publication: 6th Annual ACM-SIAM Symposium on Discrete Algorithms
publication_identifier:
isbn:
- '0898713498'
publication_status: published
publisher: Society for Industrial and Applied Mathematics
quality_controlled: '1'
related_material:
record:
- id: '11680'
relation: later_version
status: public
scopus_import: '1'
status: public
title: Average case analysis of dynamic graph algorithms
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '1995'
...