Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2505.19109 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908460061294592 |
|---|---|
| author | Maus, Yannic Ruff, Janosch |
| author_facet | Maus, Yannic Ruff, Janosch |
| 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_19109 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On Distributed Colouring of Hyperbolic Random Graphs Maus, Yannic Ruff, Janosch Data Structures and Algorithms 68W15 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. |
| title | On Distributed Colouring of Hyperbolic Random Graphs |
| topic | Data Structures and Algorithms 68W15 |
| url | https://arxiv.org/abs/2505.19109 |