5 citations · 20 across the 17 of their papers we have counts for
10 papers · 2 filters
Massively Parallel Algorithms for -Matching
Mohsen Ghaffari, Christoph Grunau, Slobodan Mitrović
This paper presents an round massively parallel algorithm for approximation of maximum weighted -matchings, using near-linear memory per machine. Her…
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…
A Nearly Tight Analysis of Greedy k-means++
Christoph Grunau, Ahmet Alper Özüdoğru, Václav Rozhoň +1
The famous -means++ algorithm of Arthur and Vassilvitskii [SODA 2007] is the most popular way of solving the -means problem in practice. The algorithm is very simple: it samp…