<p>In this paper, we study minimum weight spanning trees of the random geometric graph (RGG)&#xa0;<InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(G\)</EquationSource> <EquationSource Format="MATHML"><math> <mi>G</mi> </math></EquationSource> </InlineEquation> formed by&#xa0;<InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(n\)</EquationSource> <EquationSource Format="MATHML"><math> <mi>n</mi> </math></EquationSource> </InlineEquation> vertices distributed in the unit square according to a certain common density and a given adjacency distance. Each edge of the RGG is also equipped with a random weight that is independent of the vertex locations. For adjacency distances larger than the connectivity threshold, we use a low weight path substitution technique to obtain deviation bounds for the minimum weight of a spanning tree of the RGG. We also use martingale difference based methods to upper bound the variance and thereby derive sufficient conditions for&#xa0;<InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(L^2-\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mi>L</mi> <mn>2</mn> </msup> <mo>-</mo> </mrow> </math></EquationSource> </InlineEquation>convergence of the minimum weight, appropriately scaled and centred. Finally, we illustrate our results with an example where the edge weight cumulative distribution function (cdf) grows polynomially close to the origin.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Minimum Spanning Trees of Random Geometric Graphs with Independent Edge Weights

  • Ghurumuruhan Ganesan

摘要

In this paper, we study minimum weight spanning trees of the random geometric graph (RGG)  \(G\) G formed by  \(n\) n vertices distributed in the unit square according to a certain common density and a given adjacency distance. Each edge of the RGG is also equipped with a random weight that is independent of the vertex locations. For adjacency distances larger than the connectivity threshold, we use a low weight path substitution technique to obtain deviation bounds for the minimum weight of a spanning tree of the RGG. We also use martingale difference based methods to upper bound the variance and thereby derive sufficient conditions for  \(L^2-\) L 2 - convergence of the minimum weight, appropriately scaled and centred. Finally, we illustrate our results with an example where the edge weight cumulative distribution function (cdf) grows polynomially close to the origin.