How local constraints influence network diameter and applications to LCL generalizations
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910588234366976 |
|---|---|
| author | Bousquet, Nicolas Feuilloley, Laurent Pierron, Théo |
| author_facet | Bousquet, Nicolas Feuilloley, Laurent Pierron, Théo |
| contents | In this paper, we investigate how local rules enforced at every node can influence the topology of a network. More precisely, we establish several results on the diameter of trees as a function of the number of nodes, as listed below. These results have important consequences on the landscape of locally checkable labelings (LCL) on \emph{unbounded} degree graphs, a case in which our lack of knowledge is in striking contrast with that of \emph{bounded degree graphs}, that has been intensively studied recently. [See paper for full abstract.] |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_01305 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | How local constraints influence network diameter and applications to LCL generalizations Bousquet, Nicolas Feuilloley, Laurent Pierron, Théo Distributed, Parallel, and Cluster Computing In this paper, we investigate how local rules enforced at every node can influence the topology of a network. More precisely, we establish several results on the diameter of trees as a function of the number of nodes, as listed below. These results have important consequences on the landscape of locally checkable labelings (LCL) on \emph{unbounded} degree graphs, a case in which our lack of knowledge is in striking contrast with that of \emph{bounded degree graphs}, that has been intensively studied recently. [See paper for full abstract.] |
| title | How local constraints influence network diameter and applications to LCL generalizations |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2409.01305 |