Bernhard Haeupler

Rank-Balanced Trees

2015 · ACM Transactions on Algorithms

Since the invention of AVL trees in 1962, many kinds of binary search trees have been proposed. Notable are red-black trees, in which bottom-up rebalancing after an insertion or deletion takes O(1) amortized time and …

Deterministic Distributed Sparse and Ultra-Sparse Spanners and Connectivity Certificates

2022 · arXiv (Cornell University)

This paper presents efficient distributed algorithms for a number of fundamental problems in the area of graph sparsification: We provide the first deterministic distributed algorithm that computes an ultra-sparse spanner in $\textrm{polylog}(n)$ rounds in weighted …