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