@inproceedings{22917,
  abstract     = {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.},
  author       = {Van Der Hoog, Ivor and Iacono, John and Rotenberg, Eva and Rutschmann, Daniel P},
  booktitle    = {34th Annual European Symposium on Algorithms},
  isbn         = {9783959774451},
  issn         = {1868-8969},
  keywords     = {Data structures, graph algorithms, amortized analysis},
  location     = {L’Aquila, Italy},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Near-optimal working-set heaps and dijkstra on pointer machines}},
  doi          = {10.4230/LIPIcs.ESA.2026.45},
  volume       = {388},
  year         = {2026},
}

@article{11675,
  abstract     = {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.},
  author       = {Bhattacharya, Sayan and Chakrabarty, Deeparnab and Henzinger, Monika H},
  issn         = {1432-0541},
  journal      = {Algorithmica},
  keywords     = {Dynamic algorithms, Data structures, Graph algorithms, Matching, Vertex cover},
  number       = {4},
  pages        = {1057--1080},
  publisher    = {Springer Nature},
  title        = {{Deterministic dynamic matching in O(1) update time}},
  doi          = {10.1007/s00453-019-00630-4},
  volume       = {82},
  year         = {2020},
}

@article{11679,
  abstract     = {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 .

We 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.},
  author       = {Henzinger, Monika H and King, V. and Warnow, T.},
  issn         = {1432-0541},
  journal      = {Algorithmica},
  keywords     = {Algorithms, Data structures, Evolutionary biology, Theory of databases},
  pages        = {1--13},
  publisher    = {Springer Nature},
  title        = {{Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology}},
  doi          = {10.1007/pl00009268},
  volume       = {24},
  year         = {1999},
}