Maximum Spanning Trees of Random Geometric Graphs With Independent Edge Weights
In this paper, we study maximum weight spanning trees of the random geometric graph (RGG)~\(G\) formed by~\(n\) vertices where each edge is independently either open or closed with a certain probability and is also equipped with an independent random positive weight. We use segmentation and iterative path construction to obtain deviation bounds for the order of growth of the maximum weight of a spanning tree in terms of an inverse of the edge weight complementary cumulative distribution function (ccdf) and also illustrate our results for the special cases of power law and exponential decay.…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.08529
curl -X POST /api/v1/records/arxiv/2608.08529/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.08529/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'