On Minimum Spanning Trees for Random Euclidean Bipartite Graphs

2021/07/18 by Correddu, Mario, Trevisan, Dario
#FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.2107.08452

Abstract

We consider the minimum spanning tree problem on a weighted complete bipartite graph K_{nR, nB} whose n=n_R+n_B vertices are random, i.i.d. uniformly distributed points in the unit cube in d dimensions and edge weights are the p-th power of their Euclidean distance, with p>0. In the large n limit with n_R/n → α_R and 0

Related

• On the Random Minimum Spanning Subgraph Problem for Hypergraphs
• On the random minimum edge-disjoint spanning trees problem
• Euclidean minimum spanning trees with location dependent and power weighted edges
• Minimum Spanning Trees of Random Geometric Graphs with Location\n Dependent Weights
• The scaling limit of the minimum spanning tree of the complete graph