Showing 2024Show all
3 papers · 1 filter
cs.DS2024
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…
cs.DS2024
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…
cs.DC2024
Fast Broadcast in Highly Connected Networks
Shashwat Chandra, Yi-Jun Chang, Michal Dory +2
We revisit the classic broadcast problem, wherein we have messages, each composed of bits, distributed arbitrarily across a network. The objective is to broadcast…