186 citations · 243 across the 28 of their papers we have counts for
Showing 2022Show all
3 papers · 1 filter
cs.DS2022
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…
cs.DS2022★ 1 cited
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…
cs.DS2022
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…