Minimum Spanning Trees Across Well-Connected Cities and with Location-Dependent Weights
Ghurumuruhan Ganesan
Communications in Mathematics and Statistics ›› 2022, Vol. 10 ›› Issue (1) : 1 -50.
Minimum Spanning Trees Across Well-Connected Cities and with Location-Dependent Weights
Consider n nodes $\{X_i\}_{1 \le i \le n}$ independently and identically distributed (i.i.d.) across N cities located within the unit square S. Each city is modelled as an $r_n \times r_n$ square, and $\mathrm{{MSTC}}_n$ denotes the weighted length of the minimum spanning tree containing all the n nodes, where the edge length between nodes $X_i$ and $X_j$ is weighted by a factor that depends on the individual locations of $X_i$ and $X_j.$ We use approximation methods to obtain variance estimates for $\mathrm{{MSTC}}_n$ and prove that if the cities are well connected in a certain sense, then $\mathrm{{MSTC}}_n$ appropriately centred and scaled converges to zero in probability. Using the above proof techniques we also study $\mathrm{{MST}}_n,$ the length of the minimum weighted spanning tree for nodes distributed throughout the unit square S with location-dependent edge weights. In this case, the variance of $\mathrm{{MST}}_n$ grows at most as a power of the logarithm of n and we use a subsequence argument to get almost sure convergence of $\mathrm{{MST}}_n,$ appropriately centred and scaled.
Minimum spanning tree / Well-connected cities / Location-dependent edge weights
| [1] |
|
| [2] |
|
| [3] |
|
| [4] |
|
| [5] |
|
| [6] |
|
| [7] |
Erlebach, T., Hoffmann, M., Krizanc, D., Mihalák, M., Raman. R.: Computing minimum spanning trees with uncertainty. In: Symposium on Theoretical Aspects of Computer Science (2008) Bordeaux, pp. 277–288 (2008) |
| [8] |
|
| [9] |
|
| [10] |
|
| [11] |
|
| [12] |
|
| [13] |
|
| [14] |
Supowit, K.J., Plaisted, D.A., Reingold, E.M.: Heuristics for weighted perfect matching. In: Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing, pp. 398–419 (1980) |
/
| 〈 |
|
〉 |