---
_id: '11768'
abstract:
- lang: eng
text: "In the decremental single-source shortest paths (SSSP) problem, we want to
maintain the distances between a given source node s and every other node in an
n-node m-edge graph G undergoing edge deletions. While its static counterpart
can be solved in near-linear time, this decremental problem is much more challenging
even in the undirected unweighted case. In this case, the classic O(mn) total
update time of Even and Shiloach [16] has been the fastest known algorithm for
three decades. At the cost of a (1+ϵ)-approximation factor, the running time was
recently improved to n2+o(1) by Bernstein and Roditty [9]. In this article, we
bring the running time down to near-linear: We give a (1+ϵ)-approximation algorithm
with m1+o(1) expected total update time, thus obtaining near-linear time. Moreover,
we obtain m1+o(1) log W time for the weighted case, where the edge weights are
integers from 1 to W. The only prior work on weighted graphs in o(mn) time is
the mn0.9 + o(1)-time algorithm by Henzinger et al. [18, 19], which works for
directed graphs with quasi-polynomial edge weights. The expected running time
bound of our algorithm holds against an oblivious adversary.\r\n\r\nIn contrast
to the previous results, which rely on maintaining a sparse emulator, our algorithm
relies on maintaining a so-called sparse (h, ϵ)-hop set introduced by Cohen [12]
in the PRAM literature. An (h, ϵ)-hop set of a graph G=(V, E) is a set F of weighted
edges such that the distance between any pair of nodes in G can be (1+ϵ)-approximated
by their h-hop distance (given by a path containing at most h edges) on G′=(V,
E ∪ F). Our algorithm can maintain an (no(1), ϵ)-hop set of near-linear size in
near-linear time under edge deletions. It is the first of its kind to the best
of our knowledge. To maintain approximate distances using this hop set, we extend
the monotone Even-Shiloach tree of Henzinger et al. [20] and combine it with the
bounded-hop SSSP technique of Bernstein [4, 5] and Mądry [27]. These two new tools
might be of independent interest."
article_processing_charge: No
article_type: original
arxiv: 1
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: Sebastian
full_name: Krinninger, Sebastian
last_name: Krinninger
- first_name: Danupon
full_name: Nanongkai, Danupon
last_name: Nanongkai
citation:
ama: Henzinger MH, Krinninger S, Nanongkai D. Decremental single-source shortest
paths on undirected graphs in near-linear total update time. Journal of the
ACM. 2018;65(6):1-40. doi:10.1145/3218657
apa: Henzinger, M. H., Krinninger, S., & Nanongkai, D. (2018). Decremental single-source
shortest paths on undirected graphs in near-linear total update time. Journal
of the ACM. Association for Computing Machinery. https://doi.org/10.1145/3218657
chicago: Henzinger, Monika H, Sebastian Krinninger, and Danupon Nanongkai. “Decremental
Single-Source Shortest Paths on Undirected Graphs in near-Linear Total Update
Time.” Journal of the ACM. Association for Computing Machinery, 2018. https://doi.org/10.1145/3218657.
ieee: M. H. Henzinger, S. Krinninger, and D. Nanongkai, “Decremental single-source
shortest paths on undirected graphs in near-linear total update time,” Journal
of the ACM, vol. 65, no. 6. Association for Computing Machinery, pp. 1–40,
2018.
ista: Henzinger MH, Krinninger S, Nanongkai D. 2018. Decremental single-source shortest
paths on undirected graphs in near-linear total update time. Journal of the ACM.
65(6), 1–40.
mla: Henzinger, Monika H., et al. “Decremental Single-Source Shortest Paths on Undirected
Graphs in near-Linear Total Update Time.” Journal of the ACM, vol. 65,
no. 6, Association for Computing Machinery, 2018, pp. 1–40, doi:10.1145/3218657.
short: M.H. Henzinger, S. Krinninger, D. Nanongkai, Journal of the ACM 65 (2018)
1–40.
date_created: 2022-08-08T12:33:17Z
date_published: 2018-12-01T00:00:00Z
date_updated: 2023-02-21T16:30:41Z
day: '01'
doi: 10.1145/3218657
extern: '1'
external_id:
arxiv:
- '1512.08148'
intvolume: ' 65'
issue: '6'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1512.08148
month: '12'
oa: 1
oa_version: Preprint
page: 1-40
publication: Journal of the ACM
publication_identifier:
eissn:
- 1557-735X
issn:
- 0004-5411
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
related_material:
record:
- id: '11855'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Decremental single-source shortest paths on undirected graphs in near-linear
total update time
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 65
year: '2018'
...
---
_id: '11769'
abstract:
- lang: eng
text: "This paper solves a longstanding open problem in fully dynamic algorithms:
We present the first fully dynamic algorithms that maintain connectivity, bipartiteness,
and approximate minimum spanning trees in polylogarithmic time per edge insertion
or deletion. The algorithms are designed using a new dynamic technique that combines
a novel graph decomposition with randomization. They are Las-Vegas type randomized
algorithms which use simple data structures and have a small constant factor.\r\nLet
n denote the number of nodes in the graph. For a sequence of Ω(m0) operations,
where m0 is the number of edges in the initial graph, the expected time for p
updates is O(p log3 n) (througout the paper the logarithms are based 2) for connectivity
and bipartiteness. The worst-case time for one query is O(log n/log log n). For
the k-edge witness problem (“Does the removal of k given edges disconnect the
graph?”) the expected time for p updates is O(p log3 n) and the expected time
for q queries is O(qk log3 n). Given a graph with k different weights, the minimum
spanning tree can be maintained during a sequence of p updates in expected time
O(pk log3 n). This implies an algorithm to maintain a 1 + ε-approximation of the
minimum spanning tree in expected time O((p log3 n logU)/ε) for p updates, where
the weights of the edges are between 1 and U."
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
- first_name: Valerie
full_name: King, Valerie
last_name: King
citation:
ama: Henzinger MH, King V. Randomized fully dynamic graph algorithms with polylogarithmic
time per operation. Journal of the ACM. 1999;46(4):502-516. doi:10.1145/320211.320215
apa: Henzinger, M. H., & King, V. (1999). Randomized fully dynamic graph algorithms
with polylogarithmic time per operation. Journal of the ACM. Association
for Computing Machinery. https://doi.org/10.1145/320211.320215
chicago: Henzinger, Monika H, and Valerie King. “Randomized Fully Dynamic Graph
Algorithms with Polylogarithmic Time per Operation.” Journal of the ACM.
Association for Computing Machinery, 1999. https://doi.org/10.1145/320211.320215.
ieee: M. H. Henzinger and V. King, “Randomized fully dynamic graph algorithms with
polylogarithmic time per operation,” Journal of the ACM, vol. 46, no. 4.
Association for Computing Machinery, pp. 502–516, 1999.
ista: Henzinger MH, King V. 1999. Randomized fully dynamic graph algorithms with
polylogarithmic time per operation. Journal of the ACM. 46(4), 502–516.
mla: Henzinger, Monika H., and Valerie King. “Randomized Fully Dynamic Graph Algorithms
with Polylogarithmic Time per Operation.” Journal of the ACM, vol. 46,
no. 4, Association for Computing Machinery, 1999, pp. 502–16, doi:10.1145/320211.320215.
short: M.H. Henzinger, V. King, Journal of the ACM 46 (1999) 502–516.
date_created: 2022-08-08T12:50:25Z
date_published: 1999-07-01T00:00:00Z
date_updated: 2022-09-12T10:50:08Z
day: '01'
doi: 10.1145/320211.320215
extern: '1'
intvolume: ' 46'
issue: '4'
language:
- iso: eng
month: '07'
oa_version: None
page: 502-516
publication: Journal of the ACM
publication_identifier:
eissn:
- 1557-735X
issn:
- 0004-5411
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: Randomized fully dynamic graph algorithms with polylogarithmic time per operation
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 46
year: '1999'
...
---
_id: '4046'
abstract:
- lang: eng
text: The main contribution of this work is an O(n log n + k)-time algorithm for
computing all k intersections among n line segments in the plane. This time complexity
is easily shown to be optimal. Within the same asymptotic cost, our algorithm
can also construct the subdivision of the plane defined by the segments and compute
which segment (if any) lies right above (or below) each intersection and each
endpoint. The algorithm has been implemented and performs very well. The storage
requirement is on the order of n + k in the worst case, but it is considerably
lower in practice. To analyze the complexity of the algorithm, an amortization
argument based on a new combinatorial theorem on line arrangements is used.
acknowledgement: "B, Chazelle wishes to acknowledge the National Science Foundation
for supporting this research in part under Grant CCR 87-00917. H, Edelsbrunner is
pleased to acknowledge the support of Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862
and the NSF under Grant CCR 87-14565. Permission to copy without fee all or part
of this material is granted provided that the copies are not made or distributed
for direct commercial advantage, the ACM copyright notice and the title of the publication
and its date appear, and notice is given that copying is by permission of the Association
for\r\nComputing Machinery. To copy otherwise, or to republish, requires a fee and/or
specific permission."
article_processing_charge: No
article_type: original
author:
- first_name: Bernard
full_name: Chazelle, Bernard
last_name: Chazelle
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
citation:
ama: Chazelle B, Edelsbrunner H. An optimal algorithm for intersecting line segments
in the plane. Journal of the ACM. 1992;39(1):1-54. doi:10.1145/147508.147511
apa: Chazelle, B., & Edelsbrunner, H. (1992). An optimal algorithm for intersecting
line segments in the plane. Journal of the ACM. ACM. https://doi.org/10.1145/147508.147511
chicago: Chazelle, Bernard, and Herbert Edelsbrunner. “An Optimal Algorithm for
Intersecting Line Segments in the Plane.” Journal of the ACM. ACM, 1992.
https://doi.org/10.1145/147508.147511.
ieee: B. Chazelle and H. Edelsbrunner, “An optimal algorithm for intersecting line
segments in the plane,” Journal of the ACM, vol. 39, no. 1. ACM, pp. 1–54,
1992.
ista: Chazelle B, Edelsbrunner H. 1992. An optimal algorithm for intersecting line
segments in the plane. Journal of the ACM. 39(1), 1–54.
mla: Chazelle, Bernard, and Herbert Edelsbrunner. “An Optimal Algorithm for Intersecting
Line Segments in the Plane.” Journal of the ACM, vol. 39, no. 1, ACM, 1992,
pp. 1–54, doi:10.1145/147508.147511.
short: B. Chazelle, H. Edelsbrunner, Journal of the ACM 39 (1992) 1–54.
date_created: 2018-12-11T12:06:37Z
date_published: 1992-01-01T00:00:00Z
date_updated: 2022-03-16T08:32:17Z
day: '01'
doi: 10.1145/147508.147511
extern: '1'
intvolume: ' 39'
issue: '1'
language:
- iso: eng
main_file_link:
- url: https://dl.acm.org/doi/10.1145/147508.147511
month: '01'
oa_version: None
page: 1 - 54
publication: Journal of the ACM
publication_identifier:
eissn:
- 1557-735X
issn:
- 0004-5411
publication_status: published
publisher: ACM
publist_id: '2078'
quality_controlled: '1'
scopus_import: '1'
status: public
title: An optimal algorithm for intersecting line segments in the plane
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 39
year: '1992'
...