186 citations · 243 across the 28 of their papers we have counts for
31 papers · 1 filter
Faster All-Pairs Optimal Electric Car Routing
Dani Dorfman, Haim Kaplan, Robert E. Tarjan +2
We present a randomized -time algorithm for computing \emph{optimal energetic paths} for an electric car between all pairs of vertices in an -vertex directed…
Minimum-cost paths for electric cars
Dani Dorfman, Haim Kaplan, Robert E. Tarjan +2
An electric car equipped with a battery of a finite capacity travels on a road network with an infrastructure of charging stations. Each charging station has a possibly different c…
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…
Optimal resizable arrays
Robert E. Tarjan, Uri Zwick
A \emph{resizable array} is an array that can \emph{grow} and \emph{shrink} by the addition or removal of items from its end, or both its ends, while still supporting constant-time…
A Simpler Proof that Pairing Heaps Take O(1) Amortized Time per Insertion
Corwin Sinnamon, Robert Tarjan
The pairing heap is a simple "self-adjusting" implementation of a heap (priority queue). Inserting an item into a pairing heap or decreasing the key of an item takes O(1) time wors…
Finding Strong Components Using Depth-First Search
Robert E. Tarjan, Uri Zwick
We survey three algorithms that use depth-first search to find the strong components of a directed graph in linear time: (1) Tarjan's algorithm; (2) a cycle-finding algorithm; and…
A Tight Analysis of Slim Heaps and Smooth Heaps
Corwin Sinnamon, Robert E. Tarjan
The smooth heap and the closely related slim heap are recently invented self-adjusting implementations of the heap (priority queue) data structure. We analyze the efficiency of the…
Analysis of Smooth Heaps and Slim Heaps
Maria Hartmann, László Kozma, Corwin Sinnamon +1
The smooth heap is a recently introduced self-adjusting heap [Kozma, Saranurak, 2018] similar to the pairing heap [Fredman, Sedgewick, Sleator, Tarjan, 1986]. The smooth heap was o…
Connected Components on a PRAM in Log Diameter Time
S. Cliff Liu, Robert E. Tarjan, Peilin Zhong
We present an -time randomized PRAM algorithm for computing the connected components of an -vertex, -edge undirected graph with maximum componen…
Splaying Preorders and Postorders
Caleb C. Levy, Robert E. Tarjan
Let be a binary search tree. We prove two results about the behavior of the Splay algorithm (Sleator and Tarjan 1985). Our first result is that inserting keys into an empty bin…
A Foundation for Proving Splay is Dynamically Optimal
Caleb C. Levy, Robert E. Tarjan
Consider the task of performing a sequence of searches in a binary search tree. After each search, we allow an algorithm to arbitrarily restructure the tree. The cost of executing…
Simple Concurrent Labeling Algorithms for Connected Components
S. Cliff Liu, Robert E. Tarjan
We study a class of simple algorithms for concurrently computing the connected components of an -vertex, -edge graph. Our algorithms are easy to implement in either the COMBI…
Zip Trees
Robert E. Tarjan, Caleb C. Levy, Stephen Timmel
We introduce the zip tree, a form of randomized binary search tree that integrates previous ideas into one practical, performant, and pleasant-to-implement package. A zip tree is a…
A Note on Fault Tolerant Reachability for Directed Graphs
Loukas Georgiadis, Robert E. Tarjan
In this note we describe an application of low-high orders in fault-tolerant network design. Baswana et al. [DISC 2015] study the following reachability problem. We are given a flo…
Hollow Heaps
Thomas Dueholm Hansen, Haim Kaplan, Robert E. Tarjan +1
We introduce the hollow heap, a very simple data structure with the same amortized efficiency as the classical Fibonacci heap. All heap operations except delete and delete-min take…
Amortized Rotation Cost in AVL Trees
Mahdi Amani, Kevin A. Lai, Robert E. Tarjan
An AVL tree is the original type of balanced binary search tree. An insertion in an -node AVL tree takes at most two rotations, but a deletion in an -node AVL tree can take $…
Fibonacci Heaps Revisited
Haim Kaplan, Robert E. Tarjan, Uri Zwick
The Fibonacci heap is a classic data structure that supports deletions in logarithmic amortized time and all other heap operations in O(1) amortized time. We explore the design spa…
A Back-to-Basics Empirical Study of Priority Queues
Daniel H. Larkin, Siddhartha Sen, Robert E. Tarjan
The theory community has proposed several new heap variants in the recent past which have remained largely untested experimentally. We take the field back to the drawing board, wit…
Finding Dominators via Disjoint Set Union
Wojciech Fraczak, Loukas Georgiadis, Andrew Miller +1
The problem of finding dominators in a directed graph has many important applications, notably in global optimization of computer code. Although linear and near-linear-time algorit…
Dominator Tree Certification and Independent Spanning Trees
Loukas Georgiadis, Robert E. Tarjan
How does one verify that the output of a complicated program is correct? One can formally prove that the program is correct, but this may be beyond the power of existing methods. A…
A New Approach to Incremental Cycle Detection and Related Problems
Michael A. Bender, Jeremy T. Fineman, Seth Gilbert +1
We consider the problem of detecting a cycle in a directed graph that grows by arc insertions, and the related problems of maintaining a topological order and the strong components…