2 papers
cs.DS2026
Pure Pairing Heaps
Robert E. Tarjan, Xiaoyang Xu
The pairing heap is a "self-adjusting" implementation of a heap (priority queue) that is widely used in practice because it is simple and efficient. We introduce and analyze a simp…
cs.DS2026
Dynamic Construction of the Lovász Local Lemma
Bernhard Haeupler, Slobodan MitroviÄ, Srikkanth Ramachandran +2
This paper proves that a wide class of local search algorithms extend as is to the fully dynamic setting with an adaptive adversary, achieving an amortized number of…