6 citations · 9 across the 16 of their papers we have counts for
22 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…
DAG Projections: Reducing Distance and Flow Problems to DAGs
Bernhard Haeupler, Yonggang Jiang, Thatchaphol Saranurak
We show that every directed graph with vertices and edges admits a directed acyclic graph (DAG) with edges, called a DAG projection, that can either $(1+1/…
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…
Clustering with Label Consistency
Diptarka Chakraborty, Hendrik Fichtenberger, Bernhard Haeupler +3
Designing efficient, effective, and consistent metric clustering algorithms is a significant challenge attracting growing attention. Traditional approaches focus on the stability o…
Deterministic Negative-Weight Shortest Paths in Nearly Linear Time via Path Covers
Bernhard Haeupler, Yonggang Jiang, Thatchaphol Saranurak
We present the first deterministic nearly-linear time algorithm for single-source shortest paths with negative edge weights on directed graphs: given a directed graph with …
Reviving Thorup's Shortcut Conjecture
Aaron Bernstein, Henry Fleischmann, Maximilian Probst Gutenberg +7
We aim to revive Thorup's conjecture [Thorup, WG'92] on the existence of reachability shortcuts with ideal size-diameter tradeoffs. Thorup originally asked whether, given any graph…
Parallel -Approximate Multi-Commodity Mincost Flow in Almost Optimal Depth and Work
Bernhard Haeupler, Yonggang Jiang, Yaowei Long +2
We present a parallel algorithm for computing -approximate mincost flow on an undirected graph with edges, where capacities and costs are assigned to both edges and vert…
Simple Length-Constrained Expander Decompositions
Greg Bodwin, Bernhard Haeupler, D Ellis Hershkowitz +1
Length-constrained expander decompositions are a new graph decomposition that has led to several recent breakthroughs in fast graph algorithms. Roughly, an -length -expa…
Stronger Directed Low-Diameter Decompositions with Sub-Logarithmic Diameter and Separation
Bernhard Haeupler, Richard Hladík, Shengzhe Wang +1
This paper significantly strengthens directed low-diameter decompositions in several ways. We define and give the first results for separated low-diameter decompositions in directe…
Reducing Shortcut and Hopset Constructions to Shallow Graphs
Bernhard Haeupler, Yonggang Jiang, Thatchaphol Saranurak
We introduce a blackbox framework that simplifies all known parallel algorithms with near-linear work for single-source reachability and shortest paths in directed graphs. Specific…
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…
Constant Rate Isometric Embeddings of Hamming Metric into Edit Metric
Sudatta Bhattacharya, Sanjana Dey, Elazar Goldenberg +4
A function is called an isometric embedding of the -dimensional Hamming metric space to the -dimensional edit metric space if, for all $x,y\in\{0,…
Length-Constrained Directed Expander Decomposition and Length-Constrained Vertex-Capacitated Flow Shortcuts
Bernhard Haeupler, Yaowei Long, Thatchaphol Saranurak +1
We show the existence of length-constrained expander decomposition in directed graphs and undirected vertex-capacitated graphs. Previously, its existence was shown only in undirect…
Near-Optimal Directed Low-Diameter Decompositions
Karl Bringmann, Nick Fischer, Bernhard Haeupler +1
Low Diameter Decompositions (LDDs) are invaluable tools in the design of combinatorial graph algorithms. While historically they have been applied mainly to undirected graphs, in t…
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…
Interactive Coding with Small Memory and Improved Rate
Dorsa Fathollahi, Bernhard Haeupler, Nicolas Resch +1
In this work, we study two-party interactive coding for adversarial noise, when both parties have limited memory. We show how to convert any adaptive protocol into a protocol $…
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…
Dynamic Deterministic Constant-Approximate Distance Oracles with Worst-Case Update Time
Bernhard Haeupler, Yaowei Long, Thatchaphol Saranurak
We present a new distance oracle in the fully dynamic setting: given a weighted undirected graph with vertices undergoing both edge insertions and deletions, and an a…
Fault-Tolerant Spanners against Bounded-Degree Edge Failures: Linearly More Faults, Almost For Free
Greg Bodwin, Bernhard Haeupler, Merav Parter
We study a new and stronger notion of fault-tolerant graph structures whose size bounds depend on the degree of the failing edge set, rather than the total number of faults. For a…
Parallel, Distributed, and Quantum Exact Single-Source Shortest Paths with Negative Edge Weights
Vikrant Ashvinkumar, Aaron Bernstein, Nairen Cao +5
This paper presents parallel, distributed and quantum algorithms for single-source shortest paths when edges can have negative weights (negative-weight SSSP). We show a framework t…
Analyzing Network Coding Gossip Made Easy
Bernhard Haeupler
We give a new technique to analyze the stopping time of gossip protocols that are based on random linear network coding (RLNC). Our analysis drastically simplifies, extends and str…