186 citations · 243 across the 28 of their papers we have counts for
3 papers · 2 filters
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 $…