Local limit of Prim's algorithm
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911042399895552 |
|---|---|
| author | Corsini, Benoît Gündlach, Rowel van der Hofstad, Remco |
| author_facet | Corsini, Benoît Gündlach, Rowel van der Hofstad, Remco |
| contents | We study the local evolution of Prim's algorithm on large finite weighted graphs. When performed for $n$ steps, where $n$ is the size of the graph, Prim's algorithm will construct the minimal spanning tree (MST). We assume that our graphs converge locally in probability to some limiting rooted graph. In that case, Aldous and Steele already proved that the local limit of the MST converges to a limiting object, which can be thought of as the MST on the limiting infinite rooted graph.
Our aim is to investigate {\em how} the local limit of the MST is reached \textit{dynamically}. For this, we take $tn+o(n)$ steps of Prim, for $t\in[0,1]$, and, under some reasonable assumptions, show how the local structure interpolates between performing Prim's algorithm on the local limit when $t=0$, to the full local limit of the MST for $t=1$. Our proof relies on the use of the recently developed theory of {\em dynamic local convergence}. We further present several examples for which our assumptions, and thus our results, apply. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_04867 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Local limit of Prim's algorithm Corsini, Benoît Gündlach, Rowel van der Hofstad, Remco Probability 05C05, 05C22, 05C80, 05C85, 60K37 We study the local evolution of Prim's algorithm on large finite weighted graphs. When performed for $n$ steps, where $n$ is the size of the graph, Prim's algorithm will construct the minimal spanning tree (MST). We assume that our graphs converge locally in probability to some limiting rooted graph. In that case, Aldous and Steele already proved that the local limit of the MST converges to a limiting object, which can be thought of as the MST on the limiting infinite rooted graph. Our aim is to investigate {\em how} the local limit of the MST is reached \textit{dynamically}. For this, we take $tn+o(n)$ steps of Prim, for $t\in[0,1]$, and, under some reasonable assumptions, show how the local structure interpolates between performing Prim's algorithm on the local limit when $t=0$, to the full local limit of the MST for $t=1$. Our proof relies on the use of the recently developed theory of {\em dynamic local convergence}. We further present several examples for which our assumptions, and thus our results, apply. |
| title | Local limit of Prim's algorithm |
| topic | Probability 05C05, 05C22, 05C80, 05C85, 60K37 |
| url | https://arxiv.org/abs/2507.04867 |