Minimum spanning trees across dense cities

arXiv1801.02697MaRDI QIDQ6296170FDOQ6296170

Publication date: 8 January 2018

Abstract: Consider~(n) nodes distributed independently across~(N) cities contained with the unit square~(S) according to a distribution~(f.) Each city is modelled as an~(r_n imes r_n) square contained within~(S) and~(MSTC_n) denotes the length of the minimum spanning tree containing all the~(n) nodes. We use approximation methods to obtain variance estimates for~(MSTC_n) and prove that if the cities are well-connected and densely populated in a certain sense, then~(MSTC_n) appropriately centred and scaled converges to zero in probability. Using the proof techniques, we alternately derive corresponding results for the length~(MST_n) of the minimum spanning tree for the usual case when the nodes are independently distributed throughout the unit square~(S.) In particular, we obtain that the variance of~(MST_n) grows at most as a power of the logarithm of~(n) and use a subsequence argument to get almost sure convergence of~(MST_n) appropriately centred and scaled.

This page was built for publication: Minimum spanning trees across dense cities

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6296170)