4 papers
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…
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…
String graphs with precise number of intersections
Petr Chmel, Vít Jelínek
A string graph is an intersection graph of curves in the plane. A -string graph is a graph with a string representation in which every pair of curves intersects in at most p…
Slowdown for the geodesic-biased random walk
Mikhail Beliayeu, Petr Chmel, Bhargav Narayanan +1
Given a connected graph with some subset of its vertices excited and a fixed target vertex, in the geodesic-biased random walk on , a random walker moves as follows: from an…