15 papers
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…
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…
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…
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| \…
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…