[{"license":"https://creativecommons.org/licenses/by/4.0/","article_number":"45:1-45:13","article_processing_charge":"Yes","has_accepted_license":"1","alternative_title":["LIPIcs"],"department":[{"_id":"MoHe"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ec_funded":1,"researchdata_availability":"no","publication_status":"published","fulldoi":"https://doi.org/10.4230/LIPIcs.ESA.2026.45","date_updated":"2026-09-17T10:35:56Z","keyword":["Data structures","graph algorithms","amortized analysis"],"month":"08","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."}],"oa_version":"Published Version","das_tickbox":"0","type":"conference","external_id":{"arxiv":["2604.24134"]},"date_published":"2026-08-25T00:00:00Z","tmp":{"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)","image":"/images/cc_by.png"},"citation":{"apa":"Van Der Hoog, I., Iacono, J., Rotenberg, E., &#38; Rutschmann, D. P. (2026). Near-optimal working-set heaps and dijkstra on pointer machines. In <i>34th Annual European Symposium on Algorithms</i> (Vol. 388). L’Aquila, Italy: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2026.45\">https://doi.org/10.4230/LIPIcs.ESA.2026.45</a>","mla":"Van Der Hoog, Ivor, et al. “Near-Optimal Working-Set Heaps and Dijkstra on Pointer Machines.” <i>34th Annual European Symposium on Algorithms</i>, vol. 388, 45:1-45:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2026.45\">10.4230/LIPIcs.ESA.2026.45</a>.","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.","ieee":"I. Van Der Hoog, J. Iacono, E. Rotenberg, and D. P. Rutschmann, “Near-optimal working-set heaps and dijkstra on pointer machines,” in <i>34th Annual European Symposium on Algorithms</i>, L’Aquila, Italy, 2026, vol. 388.","chicago":"Van Der Hoog, Ivor, John Iacono, Eva Rotenberg, and Daniel P Rutschmann. “Near-Optimal Working-Set Heaps and Dijkstra on Pointer Machines.” In <i>34th Annual European Symposium on Algorithms</i>, Vol. 388. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2026.45\">https://doi.org/10.4230/LIPIcs.ESA.2026.45</a>.","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.","ama":"Van Der Hoog I, Iacono J, Rotenberg E, Rutschmann DP. Near-optimal working-set heaps and dijkstra on pointer machines. In: <i>34th Annual European Symposium on Algorithms</i>. Vol 388. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2026. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2026.45\">10.4230/LIPIcs.ESA.2026.45</a>"},"ddc":["000"],"status":"public","project":[{"name":"The design and evaluation of modern fully dynamic data structures","grant_number":"101019564","call_identifier":"H2020","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62"}],"doi":"10.4230/LIPIcs.ESA.2026.45","OA_type":"gold","year":"2026","corr_author":"1","OA_place":"publisher","language":[{"iso":"eng"}],"conference":{"location":"L’Aquila, Italy","name":"ESA: European Symposium on Algorithms","end_date":"2026-09-04","start_date":"2026-08-31"},"oa":1,"intvolume":"       388","publication":"34th Annual European Symposium on Algorithms","volume":388,"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","arxiv":1,"day":"25","publication_identifier":{"isbn":["9783959774451"],"eissn":["1868-8969"]},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","file":[{"content_type":"application/pdf","date_updated":"2026-09-17T10:33:12Z","file_name":"2026_LIPIcsESA_vanderHoog2.pdf","date_created":"2026-09-17T10:33:12Z","file_size":792024,"success":1,"checksum":"52e7cb8881060e8f17b89cd46504f445","file_id":"22949","access_level":"open_access","relation":"main_file","creator":"dernst"}],"scopus_import":"1","title":"Near-optimal working-set heaps and dijkstra on pointer machines","quality_controlled":"1","author":[{"full_name":"Van Der Hoog, Ivor","last_name":"Van Der Hoog","first_name":"Ivor"},{"full_name":"Iacono, John","last_name":"Iacono","first_name":"John"},{"first_name":"Eva","last_name":"Rotenberg","full_name":"Rotenberg, Eva"},{"last_name":"Rutschmann","id":"7397d908-b582-11f0-bf73-88b902e86527","full_name":"Rutschmann, Daniel P","first_name":"Daniel P"}],"file_date_updated":"2026-09-17T10:33:12Z","date_created":"2026-09-13T22:01:53Z","_id":"22917","supplementarymaterial":"no"},{"article_processing_charge":"No","keyword":["Dynamic algorithms","Data structures","Graph algorithms","Matching","Vertex cover"],"publication_status":"published","issue":"4","fulldoi":"https://doi.org/10.1007/s00453-019-00630-4","date_updated":"2024-11-06T12:07:43Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"journal_article","oa_version":"Published Version","abstract":[{"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.","lang":"eng"}],"month":"04","doi":"10.1007/s00453-019-00630-4","status":"public","main_file_link":[{"url":"https://doi.org/10.1007/s00453-019-00630-4","open_access":"1"}],"citation":{"ama":"Bhattacharya S, Chakrabarty D, Henzinger M. Deterministic dynamic matching in O(1) update time. <i>Algorithmica</i>. 2020;82(4):1057-1080. doi:<a href=\"https://doi.org/10.1007/s00453-019-00630-4\">10.1007/s00453-019-00630-4</a>","chicago":"Bhattacharya, Sayan, Deeparnab Chakrabarty, and Monika Henzinger. “Deterministic Dynamic Matching in O(1) Update Time.” <i>Algorithmica</i>. Springer Nature, 2020. <a href=\"https://doi.org/10.1007/s00453-019-00630-4\">https://doi.org/10.1007/s00453-019-00630-4</a>.","ista":"Bhattacharya S, Chakrabarty D, Henzinger M. 2020. Deterministic dynamic matching in O(1) update time. Algorithmica. 82(4), 1057–1080.","ieee":"S. Bhattacharya, D. Chakrabarty, and M. Henzinger, “Deterministic dynamic matching in O(1) update time,” <i>Algorithmica</i>, vol. 82, no. 4. Springer Nature, pp. 1057–1080, 2020.","short":"S. Bhattacharya, D. Chakrabarty, M. Henzinger, Algorithmica 82 (2020) 1057–1080.","apa":"Bhattacharya, S., Chakrabarty, D., &#38; Henzinger, M. (2020). Deterministic dynamic matching in O(1) update time. <i>Algorithmica</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00453-019-00630-4\">https://doi.org/10.1007/s00453-019-00630-4</a>","mla":"Bhattacharya, Sayan, et al. “Deterministic Dynamic Matching in O(1) Update Time.” <i>Algorithmica</i>, vol. 82, no. 4, Springer Nature, 2020, pp. 1057–80, doi:<a href=\"https://doi.org/10.1007/s00453-019-00630-4\">10.1007/s00453-019-00630-4</a>."},"date_published":"2020-04-01T00:00:00Z","intvolume":"        82","oa":1,"language":[{"iso":"eng"}],"year":"2020","day":"01","publication":"Algorithmica","volume":82,"author":[{"first_name":"Sayan","full_name":"Bhattacharya, Sayan","last_name":"Bhattacharya"},{"first_name":"Deeparnab","last_name":"Chakrabarty","full_name":"Chakrabarty, Deeparnab"},{"full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","first_name":"Monika H","orcid":"0000-0002-5008-6530"}],"article_type":"original","title":"Deterministic dynamic matching in O(1) update time","quality_controlled":"1","scopus_import":"1","publication_identifier":{"eissn":["1432-0541"],"issn":["0178-4617"]},"publisher":"Springer Nature","extern":"1","date_created":"2022-07-27T14:31:06Z","_id":"11675","page":"1057-1080"},{"article_type":"original","author":[{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","full_name":"Henzinger, Monika H","first_name":"Monika H","orcid":"0000-0002-5008-6530"},{"full_name":"King, V.","last_name":"King","first_name":"V."},{"first_name":"T.","full_name":"Warnow, T.","last_name":"Warnow"}],"title":"Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology","quality_controlled":"1","scopus_import":"1","publication_identifier":{"eissn":["1432-0541"],"issn":["0178-4617"]},"publisher":"Springer Nature","extern":"1","date_created":"2022-07-27T15:02:28Z","_id":"11679","page":"1-13","intvolume":"        24","language":[{"iso":"eng"}],"year":"1999","day":"01","volume":24,"publication":"Algorithmica","type":"journal_article","oa_version":"None","abstract":[{"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.","lang":"eng"}],"related_material":{"record":[{"relation":"earlier_version","id":"11927","status":"public"}]},"month":"05","doi":"10.1007/pl00009268","status":"public","citation":{"apa":"Henzinger, M., King, V., &#38; Warnow, T. (1999). Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology. <i>Algorithmica</i>. Springer Nature. <a href=\"https://doi.org/10.1007/pl00009268\">https://doi.org/10.1007/pl00009268</a>","mla":"Henzinger, Monika, et al. “Constructing a Tree from Homeomorphic Subtrees, with Applications to Computational Evolutionary Biology.” <i>Algorithmica</i>, vol. 24, Springer Nature, 1999, pp. 1–13, doi:<a href=\"https://doi.org/10.1007/pl00009268\">10.1007/pl00009268</a>.","short":"M. Henzinger, V. King, T. Warnow, Algorithmica 24 (1999) 1–13.","ieee":"M. Henzinger, V. King, and T. Warnow, “Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology,” <i>Algorithmica</i>, 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.","ama":"Henzinger M, King V, Warnow T. Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology. <i>Algorithmica</i>. 1999;24:1-13. doi:<a href=\"https://doi.org/10.1007/pl00009268\">10.1007/pl00009268</a>","chicago":"Henzinger, Monika, V. King, and T. Warnow. “Constructing a Tree from Homeomorphic Subtrees, with Applications to Computational Evolutionary Biology.” <i>Algorithmica</i>. Springer Nature, 1999. <a href=\"https://doi.org/10.1007/pl00009268\">https://doi.org/10.1007/pl00009268</a>."},"date_published":"1999-05-01T00:00:00Z","article_processing_charge":"No","keyword":["Algorithms","Data structures","Evolutionary biology","Theory of databases"],"publication_status":"published","date_updated":"2024-11-04T11:41:23Z","fulldoi":"https://doi.org/10.1007/pl00009268","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87"}]