5 citations · 8 across the 7 of their papers we have counts for
12 papers
Parallel Breadth-First Search and Exact Shortest Paths and Stronger Notions for Approximate Distances
Václav Rozhoň, Bernhard Haeupler, Anders Martinsson +2
We introduce stronger notions for approximate single-source shortest-path distances, show how to efficiently compute them from weaker standard notions, and demonstrate the algorith…
A Simple Deterministic Distributed Low-Diameter Clustering
Václav Rozhoň, Bernhard Haeupler, Christoph Grunau
We give a simple, local process for nodes in an undirected graph to form non-adjacent clusters that (1) have at most a polylogarithmic diameter and (2) contain at least half of all…
Improved Distributed Network Decomposition, Hitting Sets, and Spanners, via Derandomization
Mohsen Ghaffari, Christoph Grunau, Bernhard Haeupler +2
This paper presents significantly improved deterministic algorithms for some of the key problems in the area of distributed graph algorithms, including network decomposition, hitti…
Local Distributed Rounding: Generalized to MIS, Matching, Set Cover, and Beyond
Salwa Faour, Mohsen Ghaffari, Christoph Grunau +2
We develop a general deterministic distributed method for locally rounding fractional solutions of graph problems for which the analysis can be broken down into analyzing pairs of…
Classification of Local Problems on Paths from the Perspective of Descriptive Combinatorics
Jan Grebík, Václav Rozhoň
We classify which local problems with inputs on oriented paths have so-called Borel solution and show that this class of problems remains the same if we instead require a measurabl…
Improved Deterministic Network Decomposition
Mohsen Ghaffari, Christoph Grunau, Václav Rozhoň
Network decomposition is a central tool in distributed graph algorithms. We present two improvements on the state of the art for network decomposition, which thus lead to improveme…