18 citations · 72 across the 35 of their papers we have counts for
4 papers · 2 filters
Improved Upper Bounds for Pairing Heaps
John Iacono
Pairing heaps are shown to have constant amortized time Insert and Meld, thus showing that pairing heaps have the same amortized runtimes as Fibonacci heaps for all operations but…
Encoding 2-D Range Maximum Queries
Mordecai J. Golin, John Iacono, Danny Krizanc +3
We consider the \emph{two-dimensional range maximum query (2D-RMQ)} problem: given an array of ordered values, to pre-process it so that we can find the position of the smalles…
Confluent Persistence Revisited
Sebastien Collette, John Iacono, Stefan Langerman
It is shown how to enhance any data structure in the pointer model to make it confluently persistent, with efficient query and update times and limited space overhead. Updates are…
Using Hashing to Solve the Dictionary Problem (In External Memory)
John Iacono, Mihai Pǎtraşcu
We consider the dictionary problem in external memory and improve the update time of the well-known buffer tree by roughly a logarithmic factor. For any λ>= max {lg lg n, log_{M/B}…