6 citations · 7 across the 7 of their papers we have counts for
4 papers · 1 filter
Low-Stretch Spanning Trees via Smoothed Analysis of Dijkstra's Algorithm
Ioannis Dorkofikis, Bernhard Haeupler, Maximilian Probst Gutenberg +3
Given an undirected weighted graph , a -approximate low-stretch spanning tree (LSST) is a tree that approximates the distance metric of up to a -factor…
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…
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| \…
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…