186 citations · 243 across the 28 of their papers we have counts for
4 papers · 2 filters
Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps
Bernhard Haeupler, Richard Hladík, Václav Rozhoň +2
In this paper we prove that Dijkstra's shortest-path algorithm, if implemented with a sufficiently efficient heap, is universally optimal in its running time, and with suitable sma…
Zip-zip Trees: Making Zip Trees More Balanced, Biased, Compact, or Persistent
Ofek Gila, Michael T. Goodrich, Robert E. Tarjan
We define simple variants of zip trees, called zip-zip trees, which provide several advantages over zip trees, including overcoming a bias that favors smaller keys over larger ones…
Efficiency of Self-Adjusting Heaps
Corwin Sinnamon, Robert E. Tarjan
Since the invention of the pairing heap by Fredman, Sedgewick, Sleator, and Tarjan, it has been an open question whether this or any other simple "self-adjusting" heap supports dec…
Optimal energetic paths for electric cars
Dani Dorfman, Haim Kaplan, Robert E. Tarjan +1
A weighted directed graph , where and , describes a road network in which an electric car can roam. An arc models a road segment co…