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.

PDF
Communications in Mathematics and Statistics ›› 2022, Vol. 10 ›› Issue (1) : 1 -50. DOI: 10.1007/s40304-019-00201-7
Article

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

Author information +
History +
PDF

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

Cite this article

Download citation ▾
Ghurumuruhan Ganesan. Minimum Spanning Trees Across Well-Connected Cities and with Location-Dependent Weights. Communications in Mathematics and Statistics, 2022, 10(1): 1-50 DOI:10.1007/s40304-019-00201-7

登录浏览全文

4963

注册一个新账户 忘记密码

References

AI Summary AI Mindmap
PDF

0

Accesses

0

Citation

Detail

Sections
Recommended

AI思维导图

/