2025/05/25 by Maus, Yannic, Ruff, Janosch
#68W15 #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2505.19109
We analyse the performance of simple distributed colouring algorithms under the assumption that the input graph is a hyperbolic random graph (HRG), a generative model capturing key properties of real-world networks such as power-law degree distributions and large clustering coefficients. Motivated by the shift from worst-case analysis to more realistic network models, we study the number of rounds and size of the colour space required to colour HRGs in the distributed setting.