Minimum Spanning Trees Across Well-Connected Cities and with Location-Dependent Weights

Abstract

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.

Keywords

Minimum spanning tree / Well-connected cities / Location-dependent edge weights

References

[1] Abdel-Wahab H, Stoica I, Sultan F. A simple algorithm for computing minimum spanning trees in the internet. Inform. Comput. Sci.. 1997, 101 47-69

[2] Alexander K. The RSW theorem for continuum percolation and the CLT for Euclidean minimal spanning trees. Ann. Appl. Probab.. 1996, 6 466-494

[3] Alon N, Spencer J. The Probabilistic Method. 2008 New York: Wiley

[4] Beardwood J, Halton JH, Hammersley JM. The shortest path through many points. Proc. Camb. Philos. Soc.. 1959, 55 299-327

[5] Chatterjee S, Sen S. Minimal spanning trees and Stein’s method. Ann. Appl. Probab.. 2017, 27 1588-1645

[6] Cormen T, Leiserson CE, Rivest RR, Stein C. Introduction to Algorithms. 2009 Cambridge: MIT Press and McGraw-Hill

[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] Kesten H, Lee S. The central limit theorem for weighted minimal spanning trees on random points. Ann. Appl. Probab.. 1996, 6 495-527

[9] Penrose M, Yukich J. Weak laws of large numbers in geometric probability. Ann. Appl. Probab.. 2003, 13 277-303

[10] Penrose M. Gaussian limits for random geometric measures. Electron. J. Probab.. 2007, 12 989-1035

[11] Steele JM. Growth rates of Euclidean minimal spanning trees with power weighted edges. Ann. Probab.. 1988, 16 1767-1787

[12] Steele JM. Probability and problems in Euclidean combinatorial optimization. Stat. Sci.. 1993, 8 48-56

[13] Steele JM. Probability Theory and Combinatorial Optimization. 1997 Philadelphia: SIAM

[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)