4 papers
Density-Dependent Graph Orientation and Coloring in Scalable MPC
Mohsen Ghaffari, Christoph Grunau
This paper presents massively parallel computation (MPC) algorithms in the strongly sublinear memory regime (aka, scalable MPC) for orienting and coloring graphs as a function of i…
Towards True Work-Efficiency in Parallel Derandomization: MIS, Maximal Matching, and Hitting Set
Mohsen Ghaffari, Christoph Grunau
Derandomization is one of the classic topics studied in the theory of parallel computations, dating back to the early 1980s. Despite much work, all known techniques lead to determi…
Dynamic O(arboricity) coloring in polylogarithmic worst-case time
Mohsen Ghaffari, Christoph Grunau
A recent work by Christiansen, Nowicki, and Rotenberg provides dynamic algorithms for coloring sparse graphs, concretely as a function of the arboricity alpha of the input graph. T…
Near-Optimal Deterministic Network Decomposition and Ruling Set, and Improved MIS
Mohsen Ghaffari, Christoph Grunau
This paper improves and in two cases nearly settles, up to logarithmically lower-order factors, the deterministic complexity of some of the most central problems in distributed gra…