6 papers
Splay trees are almost dynamically optimal
Petr Chmel, Bernhard Haeupler, Richard HladÃk +5
Sleator and Tarjan [JACM, 1985] conjectured that splay trees are dynamically optimal -- that on every access sequence, they perform within a constant factor of the optimal offline…
Better Diameter Bounds for Efficient Shortcuts and a Structural Criterion for Constructiveness
Bernhard Haeupler, Antti Roeyskoe, Zhijun Zhang
All parallel algorithms for directed reachability and shortest paths crucially rely on efficient shortcut constructions. These constructions find directed paths and shortcut them b…
A Constant-Approximation Distance Labeling Scheme under Polynomially Many Edge Failures
Bernhard Haeupler, Yaowei Long, Antti Roeyskoe +1
A fault-tolerant distance labeling scheme assigns a label to each vertex and edge of an undirected weighted graph with vertices so that, for any edge set of size $|F| \…
Maintaining Routing Structures under Deletions via Self-Pruning
Bernhard Haeupler, Antti Roeyskoe
Expanders are powerful algorithmic structures with two key properties: they are a) routable: for any multi-commodity flow unit demand, there exists a routing with low congestion ov…
A Simple Parallel Algorithm with Near-Linear Work for Negative-Weight Single-Source Shortest Paths
Nick Fischer, Bernhard Haeupler, Rustam Latypov +2
We give the first parallel algorithm with optimal work for the classical problem of computing Single-Source Shortest Paths in general graphs with negative-weight edg…
Low-Step Multi-Commodity Flow Emulators
Bernhard Haeupler, D Ellis Hershkowitz, Jason Li +2
We introduce the concept of low-step multi-commodity flow emulators for any undirected, capacitated graph. At a high level, these emulators contain approximate multi-commodity flow…