47 citations · 207 across the 54 of their papers we have counts for
7 papers · 1 filter
Hop-Constrained Oblivious Routing
Mohsen Ghaffari, Bernhard Haeupler, Goran Zuzic
We prove the existence of an oblivious routing scheme that is -competitive in terms of , thus resolving a well-known question in obl…
Deterministic Distributed Vertex Coloring: Simpler, Faster, and without Network Decomposition
Mohsen Ghaffari, Fabian Kuhn
We present a simple deterministic distributed algorithm that computes a -vertex coloring in rounds. The algorithm can be implemented with $O(\log n…
Low-Congestion Shortcuts for Graphs Excluding Dense Minors
Mohsen Ghaffari, Bernhard Haeupler
We prove that any -node graph with diameter admits shortcuts with congestion and dilation , where is the maximum edge-density of any minor of $…
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…
A Massively Parallel Algorithm for Minimum Weight Vertex Cover
Mohsen Ghaffari, Ce Jin, Daan Nilis
We present a massively parallel algorithm, with near-linear memory per machine, that computes a -approximation of minimum-weight vertex cover in ro…
Massively Parallel Algorithms for Distance Approximation and Spanners
Amartya Shankha Biswas, Michal Dory, Mohsen Ghaffari +2
Over the past decade, there has been increasing interest in distributed/parallel algorithms for processing large-scale graphs. By now, we have quite fast algorithms -- usually subl…