Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2505.19109 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of Contents:
- 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.