---
OA_place: publisher
OA_type: gold
_id: '22917'
abstract:
- lang: eng
text: 'A heap is a dynamic data structure that stores a set of labeled values under
the following operations: pop returns the minimum value of the heap, Push(x_i)
pushes a new value x_i onto the heap, and DecreaseKey(i, v) decreases the value
x_i to v. A working-set heap is a heap that supports the x_i ← pop() operation
in O(log Γ(x_i)) time where Γ(x_i) is the size of the working set: the number
of elements that were pushed onto the heap while x_i was in the heap. The goal
of working set heap design is to maintain the working set property while minimizing
the overhead of the Push and DecreaseKey operations. On a word RAM, there exist
working set heaps that support Push and DecreaseKey in amortized constant time.
In this paper, we show via a simple construction that pointer machines, one of
the most general and least-assuming computational models, support working set
heaps that support Push in amortized constant time and DecreaseKey in inverse-Ackermann
time. A by-product of this analysis is that Dijkstra’s shortest path algorithm
can be near-universally optimal on a pointer machine - incurring only an additive
O(m α(m)) overhead compared to the optimal running time for distance ordering,
where m denotes the number of edges in the graph.'
acknowledgement: "Ivor van der Hoog, Eva Rotenberg, and Daniel Rutschmann thank the
VILLUM Foundation\r\ngrant (VIL37507) “Efficient Recomputations for Changeful Problems”
for supporting this work.\r\nDaniel Rutschmann is supported by the European Research
Council (ERC) under the European\r\nUnion’s Horizon 2020 research and innovation
programme (No. 101019564) . John Iacono\r\nis supported by the Fonds de la Recherche
Scientifique – FNRS.This work started at Dagstuhl 25191: Adaptive and Scalable Data
Structures.\r\n\r\n"
alternative_title:
- LIPIcs
article_number: 45:1-45:13
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Ivor
full_name: Van Der Hoog, Ivor
last_name: Van Der Hoog
- first_name: John
full_name: Iacono, John
last_name: Iacono
- first_name: Eva
full_name: Rotenberg, Eva
last_name: Rotenberg
- first_name: Daniel P
full_name: Rutschmann, Daniel P
id: 7397d908-b582-11f0-bf73-88b902e86527
last_name: Rutschmann
citation:
ama: 'Van Der Hoog I, Iacono J, Rotenberg E, Rutschmann DP. Near-optimal working-set
heaps and dijkstra on pointer machines. In: 34th Annual European Symposium
on Algorithms. Vol 388. Schloss Dagstuhl - Leibniz-Zentrum für Informatik;
2026. doi:10.4230/LIPIcs.ESA.2026.45'
apa: 'Van Der Hoog, I., Iacono, J., Rotenberg, E., & Rutschmann, D. P. (2026).
Near-optimal working-set heaps and dijkstra on pointer machines. In 34th Annual
European Symposium on Algorithms (Vol. 388). L’Aquila, Italy: Schloss Dagstuhl
- Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ESA.2026.45'
chicago: Van Der Hoog, Ivor, John Iacono, Eva Rotenberg, and Daniel P Rutschmann.
“Near-Optimal Working-Set Heaps and Dijkstra on Pointer Machines.” In 34th
Annual European Symposium on Algorithms, Vol. 388. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2026. https://doi.org/10.4230/LIPIcs.ESA.2026.45.
ieee: I. Van Der Hoog, J. Iacono, E. Rotenberg, and D. P. Rutschmann, “Near-optimal
working-set heaps and dijkstra on pointer machines,” in 34th Annual European
Symposium on Algorithms, L’Aquila, Italy, 2026, vol. 388.
ista: 'Van Der Hoog I, Iacono J, Rotenberg E, Rutschmann DP. 2026. Near-optimal
working-set heaps and dijkstra on pointer machines. 34th Annual European Symposium
on Algorithms. ESA: European Symposium on Algorithms, LIPIcs, vol. 388, 45:1-45:13.'
mla: Van Der Hoog, Ivor, et al. “Near-Optimal Working-Set Heaps and Dijkstra on
Pointer Machines.” 34th Annual European Symposium on Algorithms, vol. 388,
45:1-45:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:10.4230/LIPIcs.ESA.2026.45.
short: I. Van Der Hoog, J. Iacono, E. Rotenberg, D.P. Rutschmann, in:, 34th Annual
European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2026.
conference:
end_date: 2026-09-04
location: L’Aquila, Italy
name: 'ESA: European Symposium on Algorithms'
start_date: 2026-08-31
corr_author: '1'
das_tickbox: '0'
date_created: 2026-09-13T22:01:53Z
date_published: 2026-08-25T00:00:00Z
date_updated: 2026-09-17T10:35:56Z
day: '25'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.ESA.2026.45
ec_funded: 1
external_id:
arxiv:
- '2604.24134'
file:
- access_level: open_access
checksum: 52e7cb8881060e8f17b89cd46504f445
content_type: application/pdf
creator: dernst
date_created: 2026-09-17T10:33:12Z
date_updated: 2026-09-17T10:33:12Z
file_id: '22949'
file_name: 2026_LIPIcsESA_vanderHoog2.pdf
file_size: 792024
relation: main_file
success: 1
file_date_updated: 2026-09-17T10:33:12Z
fulldoi: https://doi.org/10.4230/LIPIcs.ESA.2026.45
has_accepted_license: '1'
intvolume: ' 388'
keyword:
- Data structures
- graph algorithms
- amortized analysis
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
project:
- _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62
call_identifier: H2020
grant_number: '101019564'
name: The design and evaluation of modern fully dynamic data structures
publication: 34th Annual European Symposium on Algorithms
publication_identifier:
eissn:
- 1868-8969
isbn:
- '9783959774451'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: Near-optimal working-set heaps and dijkstra on pointer machines
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 388
year: '2026'
...
---
_id: '11675'
abstract:
- lang: eng
text: 'We consider the problems of maintaining an approximate maximum matching and
an approximate minimum vertex cover in a dynamic graph undergoing a sequence of
edge insertions/deletions. Starting with the seminal work of Onak and Rubinfeld
(in: Proceedings of the ACM symposium on theory of computing (STOC), 2010), this
problem has received significant attention in recent years. Very recently, extending
the framework of Baswana et al. (in: Proceedings of the IEEE symposium on foundations
of computer science (FOCS), 2011) , Solomon (in: Proceedings of the IEEE symposium
on foundations of computer science (FOCS), 2016) gave a randomized dynamic algorithm
for this problem that has an approximation ratio of 2 and an amortized update
time of O(1) with high probability. This algorithm requires the assumption of
an oblivious adversary, meaning that the future sequence of edge insertions/deletions
in the graph cannot depend in any way on the algorithm’s past output. A natural
way to remove the assumption on oblivious adversary is to give a deterministic
dynamic algorithm for the same problem in O(1) update time. In this paper, we
resolve this question. We present a new deterministic fully dynamic algorithm
that maintains a O(1)-approximate minimum vertex cover and maximum fractional
matching, with an amortized update time of O(1). Previously, the best deterministic
algorithm for this problem was due to Bhattacharya et al. (in: Proceedings of
the ACM-SIAM symposium on discrete algorithms (SODA), 2015); it had an approximation
ratio of (2+ε) and an amortized update time of O(logn/ε2). Our result can be generalized
to give a fully dynamic O(f3)-approximate algorithm with O(f2) amortized update
time for the hypergraph vertex cover and fractional hypergraph matching problem,
where every hyperedge has at most f vertices.'
article_processing_charge: No
article_type: original
author:
- first_name: Sayan
full_name: Bhattacharya, Sayan
last_name: Bhattacharya
- first_name: Deeparnab
full_name: Chakrabarty, Deeparnab
last_name: Chakrabarty
- 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: Bhattacharya S, Chakrabarty D, Henzinger M. Deterministic dynamic matching
in O(1) update time. Algorithmica. 2020;82(4):1057-1080. doi:10.1007/s00453-019-00630-4
apa: Bhattacharya, S., Chakrabarty, D., & Henzinger, M. (2020). Deterministic
dynamic matching in O(1) update time. Algorithmica. Springer Nature. https://doi.org/10.1007/s00453-019-00630-4
chicago: Bhattacharya, Sayan, Deeparnab Chakrabarty, and Monika Henzinger. “Deterministic
Dynamic Matching in O(1) Update Time.” Algorithmica. Springer Nature, 2020.
https://doi.org/10.1007/s00453-019-00630-4.
ieee: S. Bhattacharya, D. Chakrabarty, and M. Henzinger, “Deterministic dynamic
matching in O(1) update time,” Algorithmica, vol. 82, no. 4. Springer Nature,
pp. 1057–1080, 2020.
ista: Bhattacharya S, Chakrabarty D, Henzinger M. 2020. Deterministic dynamic matching
in O(1) update time. Algorithmica. 82(4), 1057–1080.
mla: Bhattacharya, Sayan, et al. “Deterministic Dynamic Matching in O(1) Update
Time.” Algorithmica, vol. 82, no. 4, Springer Nature, 2020, pp. 1057–80,
doi:10.1007/s00453-019-00630-4.
short: S. Bhattacharya, D. Chakrabarty, M. Henzinger, Algorithmica 82 (2020) 1057–1080.
date_created: 2022-07-27T14:31:06Z
date_published: 2020-04-01T00:00:00Z
date_updated: 2024-11-06T12:07:43Z
day: '01'
doi: 10.1007/s00453-019-00630-4
extern: '1'
fulldoi: https://doi.org/10.1007/s00453-019-00630-4
intvolume: ' 82'
issue: '4'
keyword:
- Dynamic algorithms
- Data structures
- Graph algorithms
- Matching
- Vertex cover
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1007/s00453-019-00630-4
month: '04'
oa: 1
oa_version: Published Version
page: 1057-1080
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: Deterministic dynamic matching in O(1) update time
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 82
year: '2020'
...
---
_id: '11679'
abstract:
- lang: eng
text: "We are given a set T = {T 1 ,T 2 , . . .,T k } of rooted binary trees, each
T i leaf-labeled by a subset L(Ti)⊂{1,2,...,n} . If T is a tree on {1,2, . . .,n
}, we let T|L denote the minimal subtree of T induced by the nodes of L and all
their ancestors. The consensus tree problem asks whether there exists a tree T
* such that, for every i , T∗|L(Ti) is homeomorphic to T i .\r\n\r\nWe present
algorithms which test if a given set of trees has a consensus tree and if so,
construct one. The deterministic algorithm takes time min{O(N n 1/2 ), O(N+ n
2 log n )}, where N=∑i|Ti| , and uses linear space. The randomized algorithm takes
time O(N log3 n) and uses linear space. The previous best for this problem was
a 1981 O(Nn) algorithm by Aho et al. Our faster deterministic algorithm uses a
new efficient algorithm for the following interesting dynamic graph problem: Given
a graph G with n nodes and m edges and a sequence of b batches of one or more
edge deletions, then, after each batch, either find a new component that has just
been created or determine that there is no such component. For this problem, we
have a simple algorithm with running time O(n 2 log n + b 0 min{n 2 , m log n
}), where b 0 is the number of batches which do not result in a new component.
For our particular application, b0≤1 . If all edges are deleted, then the best
previously known deterministic algorithm requires time O(mn−−√) to solve this
problem. We also present two applications of these consensus tree algorithms which
solve other problems in computational evolutionary biology."
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: V.
full_name: King, V.
last_name: King
- first_name: T.
full_name: Warnow, T.
last_name: Warnow
citation:
ama: Henzinger M, King V, Warnow T. Constructing a tree from homeomorphic subtrees,
with applications to computational evolutionary biology. Algorithmica.
1999;24:1-13. doi:10.1007/pl00009268
apa: Henzinger, M., King, V., & Warnow, T. (1999). Constructing a tree from
homeomorphic subtrees, with applications to computational evolutionary biology.
Algorithmica. Springer Nature. https://doi.org/10.1007/pl00009268
chicago: Henzinger, Monika, V. King, and T. Warnow. “Constructing a Tree from Homeomorphic
Subtrees, with Applications to Computational Evolutionary Biology.” Algorithmica.
Springer Nature, 1999. https://doi.org/10.1007/pl00009268.
ieee: M. Henzinger, V. King, and T. Warnow, “Constructing a tree from homeomorphic
subtrees, with applications to computational evolutionary biology,” Algorithmica,
vol. 24. Springer Nature, pp. 1–13, 1999.
ista: Henzinger M, King V, Warnow T. 1999. Constructing a tree from homeomorphic
subtrees, with applications to computational evolutionary biology. Algorithmica.
24, 1–13.
mla: Henzinger, Monika, et al. “Constructing a Tree from Homeomorphic Subtrees,
with Applications to Computational Evolutionary Biology.” Algorithmica,
vol. 24, Springer Nature, 1999, pp. 1–13, doi:10.1007/pl00009268.
short: M. Henzinger, V. King, T. Warnow, Algorithmica 24 (1999) 1–13.
date_created: 2022-07-27T15:02:28Z
date_published: 1999-05-01T00:00:00Z
date_updated: 2024-11-04T11:41:23Z
day: '01'
doi: 10.1007/pl00009268
extern: '1'
fulldoi: https://doi.org/10.1007/pl00009268
intvolume: ' 24'
keyword:
- Algorithms
- Data structures
- Evolutionary biology
- Theory of databases
language:
- iso: eng
month: '05'
oa_version: None
page: 1-13
publication: Algorithmica
publication_identifier:
eissn:
- 1432-0541
issn:
- 0178-4617
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '11927'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Constructing a tree from homeomorphic subtrees, with applications to computational
evolutionary biology
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 24
year: '1999'
...