Showing cs.DSShow all
2 papers · 1 filter
cs.DS2026
Splay trees are almost dynamically optimal
Petr Chmel, Bernhard Haeupler, Richard Hladík +5
Sleator and Tarjan [JACM, 1985] conjectured that splay trees are dynamically optimal -- that on every access sequence, they perform within a constant factor of the optimal offline…
cs.DS2026
Frontier Space-Time Algorithms Using Only Full Memory
Petr Chmel, Aditi Dudeja, Michal Koucký +2
We develop catalytic algorithms for fundamental problems in algorithm design that run in polynomial time, use only workspace, and use sublinear catalytic spa…