Minimal spanning trees for graphs with random edge lengths
A finite connected simple graph \(G\) has independent identically distributed edge lengths and \(L\) is the minimal sum of the lengths of any spanning tree of \(G.\) It is shown that \(L\) has an integral representation that allows the expected value \(EL\) to be given in terms of the Tutte polynomial of \(G.\) For \(G\) equal to the complete graph on \(n\) vertices, this leads to an explicit exact formula for \(EL\) for \(n\) up to \(9.\) The paper also contains related results based on Poisson weighted infinite trees, Poisson Galton-Watson trees, and the theory of local weak convergence. For the entire collection see [Zbl 0997.00016].
- The expected value of random minimal length spanning tree of a complete graph
- Expected lengths of minimum spanning trees for non-identical edge distributions
- On random minimum length spanning trees
- On the value of a random minimum spanning tree problem
- On the length of a random minimum spanning tree
- On average edge length of minimum spanning trees
- Minimal spanning trees on infinite sets
- Stable matchings in high dimensions via the Poisson-weighted infinite tree
- Extremal paths in inhomogenous random graphs
- The densest subgraph problem in sparse random graphs
- The expected value of random minimal length spanning tree of a complete graph
- On the random 2-stage minimum spanning tree
- On finding a minimum spanning tree in a network with random weights
- The Expected Length of a Minimal Spanning Tree of a Cylinder Graph
- OPTIMAL PATH AND MINIMAL SPANNING TREES IN RANDOM WEIGHTED NETWORKS
- On the difference of expected lengths of minimum spanning trees
- scientific article; zbMATH DE number 4039929 (Why is no real title available?)
- Approximations for the Random Minimal Spanning Tree with Application to Network Provisioning
- Minimal spanning tree and percolation on mosaics: graph theory and percolation
- A sharp threshold for minimum bounded-depth and bounded-diameter spanning trees and Steiner trees in random networks
- scientific article; zbMATH DE number 1750458 (Why is no real title available?)
- Lévy-Khintchine random matrices and the Poisson weighted infinite skeleton tree
- Polynomial representation for the expected length of minimal spanning trees
- Minimal vertex covers of random trees
- A fractal dimension for measures via persistent homology
- On the length of a random minimum spanning tree
- The expected degree of minimal spanning forests
- On minimum spanning trees for random Euclidean bipartite graphs
- ``Minimax length links of a dissimilarity matrix and minimum spanning trees
- Minimum spanning trees of random geometric graphs with independent edge weights
- Local limit of the random degree constrained process
- A generalization of the Beraha-Kahane-Weiss theorem with graph polynomial applications
- Minimum spanning trees in networks with varying edge weights
- On random minimum length spanning trees
- Expected lengths of minimum spanning trees for non-identical edge distributions
This page was built for publication: Minimal spanning trees for graphs with random edge lengths
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4428911)
