---
_id: '15267'
abstract:
- lang: eng
text: "We study two fundamental communication primitives: broadcasting and leader
election in the classical model of multi-hop radio networks with unknown topology
and without collision detection mechanisms. It has been known for almost 20 years
that in undirected networks with n nodes and diameter D, randomized broadcasting
requires Ω(D log n/D + log2 n) rounds, assuming that uninformed nodes are not
allowed to communicate (until they are informed). Only very recently, Haeupler
and Wajc (PODC'2016) showed that this bound can be improved for the model with
spontaneous transmissions, providing an O(D log n log log n/log D + logO(1) n)-time
broadcasting algorithm. In this article, we give a new and faster algorithm that
completes broadcasting in O(D log n/log D + logO(1) n) time, succeeding with high
probability. This yields the first optimal O(D)-time broadcasting algorithm whenever
n is polynomial in D.\r\n\r\nFurthermore, our approach can be applied to design
a new leader election algorithm that matches the performance of our broadcasting
algorithm. Previously, all fast randomized leader election algorithms have used
broadcasting as a subroutine and their complexity has been asymptotically strictly
larger than the complexity of broadcasting. In particular, the fastest previously
known randomized leader election algorithm of Ghaffari and Haeupler (SODA'2013)
requires O(D log n/D min {log log n, log n/D} + logO(1) n)-time, succeeding with
high probability. Our new algorithm again requires O(D log n/log D + logO(1) n)
time, also succeeding with high probability."
article_number: '13'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Artur
full_name: Czumaj, Artur
last_name: Czumaj
- first_name: Peter
full_name: Davies, Peter
id: 11396234-BB50-11E9-B24C-90FCE5697425
last_name: Davies
orcid: 0000-0002-5646-9524
citation:
ama: Czumaj A, Davies P. Exploiting spontaneous transmissions for broadcasting and
leader election in radio networks. Journal of the ACM. 2021;68(2). doi:10.1145/3446383
apa: Czumaj, A., & Davies, P. (2021). Exploiting spontaneous transmissions for
broadcasting and leader election in radio networks. Journal of the ACM.
ACM. https://doi.org/10.1145/3446383
chicago: Czumaj, Artur, and Peter Davies. “Exploiting Spontaneous Transmissions
for Broadcasting and Leader Election in Radio Networks.” Journal of the ACM.
ACM, 2021. https://doi.org/10.1145/3446383.
ieee: A. Czumaj and P. Davies, “Exploiting spontaneous transmissions for broadcasting
and leader election in radio networks,” Journal of the ACM, vol. 68, no.
2. ACM, 2021.
ista: Czumaj A, Davies P. 2021. Exploiting spontaneous transmissions for broadcasting
and leader election in radio networks. Journal of the ACM. 68(2), 13.
mla: Czumaj, Artur, and Peter Davies. “Exploiting Spontaneous Transmissions for
Broadcasting and Leader Election in Radio Networks.” Journal of the ACM,
vol. 68, no. 2, 13, ACM, 2021, doi:10.1145/3446383.
short: A. Czumaj, P. Davies, Journal of the ACM 68 (2021).
date_created: 2024-04-03T07:41:46Z
date_published: 2021-01-28T00:00:00Z
date_updated: 2026-08-12T14:03:54Z
day: '28'
department:
- _id: DaAl
doi: 10.1145/3446383
external_id:
arxiv:
- '1703.01859'
fulldoi: https://doi.org/10.1145/3446383
intvolume: ' 68'
issue: '2'
keyword:
- Artificial Intelligence
- Hardware and Architecture
- Information Systems
- Control and Systems Engineering
- Software
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.1703.01859
month: '01'
oa: 1
oa_version: Preprint
publication: Journal of the ACM
publication_identifier:
eissn:
- 1557-735X
issn:
- 0004-5411
publication_status: published
publisher: ACM
quality_controlled: '1'
status: public
title: Exploiting spontaneous transmissions for broadcasting and leader election in
radio networks
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 68
year: '2021'
...
---
_id: '6752'
abstract:
- lang: eng
text: 'Two-player games on graphs are widely studied in formal methods, as they
model the interaction between a system and its environment. The game is played
by moving a token throughout a graph to produce an infinite path. There are several
common modes to determine how the players move the token through the graph; e.g.,
in turn-based games the players alternate turns in moving the token. We study
the bidding mode of moving the token, which, to the best of our knowledge, has
never been studied in infinite-duration games. The following bidding rule was
previously defined and called Richman bidding. Both players have separate budgets,
which sum up to 1. In each turn, a bidding takes place: Both players submit bids
simultaneously, where a bid is legal if it does not exceed the available budget,
and the higher bidder pays his bid to the other player and moves the token. The
central question studied in bidding games is a necessary and sufficient initial
budget for winning the game: a threshold budget in a vertex is a value t ∈ [0,
1] such that if Player 1’s budget exceeds t, he can win the game; and if Player
2’s budget exceeds 1 − t, he can win the game. Threshold budgets were previously
shown to exist in every vertex of a reachability game, which have an interesting
connection with random-turn games—a sub-class of simple stochastic games in which
the player who moves is chosen randomly. We show the existence of threshold budgets
for a qualitative class of infinite-duration games, namely parity games, and a
quantitative class, namely mean-payoff games. The key component of the proof is
a quantitative solution to strongly connected mean-payoff bidding games in which
we extend the connection with random-turn games to these games, and construct
explicit optimal strategies for both players.'
article_number: '31'
article_processing_charge: No
arxiv: 1
author:
- first_name: Guy
full_name: Avni, Guy
id: 463C8BC2-F248-11E8-B48F-1D18A9856A87
last_name: Avni
orcid: 0000-0001-5588-8287
- 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: Ventsislav K
full_name: Chonev, Ventsislav K
id: 36CBE2E6-F248-11E8-B48F-1D18A9856A87
last_name: Chonev
citation:
ama: Avni G, Henzinger TA, Chonev VK. Infinite-duration bidding games. Journal
of the ACM. 2019;66(4). doi:10.1145/3340295
apa: Avni, G., Henzinger, T. A., & Chonev, V. K. (2019). Infinite-duration bidding
games. Journal of the ACM. ACM. https://doi.org/10.1145/3340295
chicago: Avni, Guy, Thomas A Henzinger, and Ventsislav K Chonev. “Infinite-Duration
Bidding Games.” Journal of the ACM. ACM, 2019. https://doi.org/10.1145/3340295.
ieee: G. Avni, T. A. Henzinger, and V. K. Chonev, “Infinite-duration bidding games,”
Journal of the ACM, vol. 66, no. 4. ACM, 2019.
ista: Avni G, Henzinger TA, Chonev VK. 2019. Infinite-duration bidding games. Journal
of the ACM. 66(4), 31.
mla: Avni, Guy, et al. “Infinite-Duration Bidding Games.” Journal of the ACM,
vol. 66, no. 4, 31, ACM, 2019, doi:10.1145/3340295.
short: G. Avni, T.A. Henzinger, V.K. Chonev, Journal of the ACM 66 (2019).
date_created: 2019-08-04T21:59:16Z
date_published: 2019-07-16T00:00:00Z
date_updated: 2025-07-10T11:53:47Z
day: '16'
department:
- _id: ToHe
doi: 10.1145/3340295
external_id:
arxiv:
- '1705.01433'
isi:
- '000487714900008'
fulldoi: https://doi.org/10.1145/3340295
intvolume: ' 66'
isi: 1
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1705.01433
month: '07'
oa: 1
oa_version: Preprint
project:
- _id: 25F42A32-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z211
name: Formal methods for the design and analysis of complex systems
- _id: 25F2ACDE-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11402-N23
name: Rigorous Systems Engineering
- _id: 264B3912-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: M02369
name: Formal Methods meets Algorithmic Game Theory
publication: Journal of the ACM
publication_identifier:
eissn:
- 1557-735X
issn:
- 0004-5411
publication_status: published
publisher: ACM
quality_controlled: '1'
related_material:
record:
- id: '950'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Infinite-duration bidding games
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 66
year: '2019'
...
---
_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 M, 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., 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, 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. 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 M, 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, 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. 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: 2024-11-06T12:18:17Z
day: '01'
doi: 10.1145/3218657
extern: '1'
external_id:
arxiv:
- '1512.08148'
fulldoi: https://doi.org/10.1145/3218657
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'
...
---
OA_type: closed access
_id: '3979'
abstract:
- lang: eng
text: Protein-protein interactions, which form the basis for most cellular processes,
result in the formation of protein interfaces. Believing that the local shape
of proteins is crucial, we take a geometric approach and present a definition
of an interface surface formed by two or more proteins as a subset of their Voronoi
diagram. The definition deals with the difficult and important problem of specifying
interface boundaries by invoking methods used in the alpha shape representation
of molecules, the discrete flow on Delaunay simplices to define pockets and reconstruct
surfaces, and the assessment of the importance of topological features. We present
an algorithm to construct the surface and define a hierarchy that distinguishes
core and peripheral regions. This hierarchy is shown to have correlation with
hot-spots in protein-protein interactions. Finally, we study the geometric and
topological properties of interface surfaces and show their high degree of contortion.
article_processing_charge: No
article_type: original
author:
- first_name: Yih
full_name: Ban, Yih
last_name: Ban
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Johannes
full_name: Rudolph, Johannes
last_name: Rudolph
citation:
ama: Ban Y, Edelsbrunner H, Rudolph J. Interface surfaces for protein-protein complexes.
Journal of the ACM. 2006;53(3):361-378. doi:10.1145/1147954.1147957
apa: Ban, Y., Edelsbrunner, H., & Rudolph, J. (2006). Interface surfaces for
protein-protein complexes. Journal of the ACM. ACM. https://doi.org/10.1145/1147954.1147957
chicago: Ban, Yih, Herbert Edelsbrunner, and Johannes Rudolph. “Interface Surfaces
for Protein-Protein Complexes.” Journal of the ACM. ACM, 2006. https://doi.org/10.1145/1147954.1147957.
ieee: Y. Ban, H. Edelsbrunner, and J. Rudolph, “Interface surfaces for protein-protein
complexes,” Journal of the ACM, vol. 53, no. 3. ACM, pp. 361–378, 2006.
ista: Ban Y, Edelsbrunner H, Rudolph J. 2006. Interface surfaces for protein-protein
complexes. Journal of the ACM. 53(3), 361–378.
mla: Ban, Yih, et al. “Interface Surfaces for Protein-Protein Complexes.” Journal
of the ACM, vol. 53, no. 3, ACM, 2006, pp. 361–78, doi:10.1145/1147954.1147957.
short: Y. Ban, H. Edelsbrunner, J. Rudolph, Journal of the ACM 53 (2006) 361–378.
date_created: 2018-12-11T12:06:14Z
date_published: 2006-05-01T00:00:00Z
date_updated: 2026-08-26T11:21:19Z
day: '01'
doi: 10.1145/1147954.1147957
extern: '1'
fulldoi: https://doi.org/10.1145/1147954.1147957
intvolume: ' 53'
issue: '3'
language:
- iso: eng
month: '05'
oa_version: None
page: 361 - 378
publication: Journal of the ACM
publication_identifier:
eissn:
- 1557-735X
issn:
- 0004-5411
publication_status: published
publisher: ACM
publist_id: '2147'
status: public
title: Interface surfaces for protein-protein complexes
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 53
year: '2006'
...
---
_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 M, 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., & 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, 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. 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 M, King V. 1999. Randomized fully dynamic graph algorithms with
polylogarithmic time per operation. Journal of the ACM. 46(4), 502–516.
mla: Henzinger, Monika, 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. 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: 2024-11-06T08:15:30Z
day: '01'
doi: 10.1145/320211.320215
extern: '1'
fulldoi: https://doi.org/10.1145/320211.320215
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'
fulldoi: https://doi.org/10.1145/147508.147511
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'
...