3 citations · 3 across the 4 of their papers we have counts for
9 papers · 1 filter
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…
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…