6 citations · 7 across the 7 of their papers we have counts for
9 papers
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…
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…
Polylog-Competitive Deterministic Local Routing and Scheduling
Bernhard Haeupler, Shyamal Patel, Antti Roeyskoe +2
This paper addresses point-to-point packet routing in undirected networks, which is the most important communication primitive in most networks. The main result proves the existenc…
Sparse Semi-Oblivious Routing: Few Random Paths Suffice
Goran Zuzic, Bernhard Haeupler, Antti Roeyskoe
The packet routing problem asks to select routing paths that minimize the maximum edge congestion for a set of packets specified by source-destination vertex pairs. We revisit a se…