On finding a minimum spanning tree in a network with random weights

DOI10.1002/(SICI)1098-2418(199701/03)10:1/2%3C187::AID-RSA10%3E3.0.CO;2-6zbMATH Open0872.60008OpenAlexW2024533455MaRDI QIDQ3122913FDOQ3122913

Authors Theodore Johnson, Harold S. Stone, Colin McDiarmid

Publication date 1 October 1997

Full work available at URL https://doi.org/10.1002/(sici)1098-2418(199701/03)10:1/2%3C187::aid-rsa10%3E3.0.co;2-6

zbMATH Keywords

minimum spanning treeindependent identically distributed random weights

Mathematics Subject Classification ID

Trees (05C05) Combinatorial probability (60C05) Applications of Markov renewal processes (reliability, queueing networks, etc.) (60K20)

Recommendations

• A randomly weighted minimum spanning tree with a random cost constraint
• A randomly weighted minimum spanning tree with a random cost constraint
• OPTIMAL PATH AND MINIMAL SPANNING TREES IN RANDOM WEIGHTED NETWORKS
• On the value of a random minimum spanning tree problem
• Minimum spanning trees in networks with varying edge weights
• scientific article; zbMATH DE number 1984546
• Approximations for the Random Minimal Spanning Tree with Application to Network Provisioning
• Minimum spanning trees of random geometric graphs with location dependent weights
• On random minimum length spanning trees

Cites work

• scientific article; zbMATH DE number 53861 (Why is no real title available?)
• A note on two problems in connexion with graphs
• A random tree model associated with random graphs
• Asymptotic fringe distributions for general families of random trees
• Components of Random Forests
• Note on the heights of random recursive trees and random m‐ary search trees
• On Finding the Expected Length of a Random Minimal Tree
• On random minimum length spanning trees
• On the value of a random minimum spanning tree problem
• Random recursive forests
• The continuum random tree. I
• The minimal spanning tree in a complete graph and a functional limit theorem for trees in a random graph
• The minimum spanning tree constant in geometrical probability and under the independent model: A unified approach

Cited in

(17)

• Successive minimum spanning trees
• On the probabilistic min spanning tree problem
• Multisource invasion percolation on the complete graph
• OPTIMAL PATH AND MINIMAL SPANNING TREES IN RANDOM WEIGHTED NETWORKS
• Bounding Distributions for the Weight of a Minimum Spanning Tree in Stochastic Networks
• Invasion percolation on the Poisson-weighted infinite tree
• A randomized linear-time algorithm for finding minimum spanning trees (extended abstract)
• Approximations for the Random Minimal Spanning Tree with Application to Network Provisioning
• Randomization Helps Computing a Minimum Spanning Tree under Uncertainty
• On the value of a random minimum weight Steiner tree
• Geometry of minimum spanning trees on scale-free networks
• Minimum spanning trees in networks with varying edge weights
• Minimal spanning trees in undirected networks with exponentially distributed arc weights
• The expected complexity of Prim's minimum spanning tree algorithm
• Note on the structure of Kruskal's algorithm
• Critical random graphs and the structure of a minimum spanning tree
• GHS algorithm on a graph with random weights

This page was built for publication: On finding a minimum spanning tree in a network with random weights

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