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

Harold S. Stone, Colin McDiarmid, Theodore Johnson

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)

Cites Work

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

Cited In (9)

• Note on the structure of Kruskal's algorithm
• Minimum spanning trees in networks with varying edge weights
• Invasion percolation on the Poisson-weighted infinite tree
• Multisource invasion percolation on the complete graph
• OPTIMAL PATH AND MINIMAL SPANNING TREES IN RANDOM WEIGHTED NETWORKS
• Randomization Helps Computing a Minimum Spanning Tree under Uncertainty
• A randomized linear-time algorithm for finding minimum spanning trees (extended abstract)
• On the probabilistic min spanning tree problem
• Approximations for the Random Minimal Spanning Tree with Application to Network Provisioning

Recommendations

• Title not available (Why is that?) 👍 👎
• On the value of a random minimum spanning tree problem 👍 👎
• On random minimum length spanning trees 👍 👎
• OPTIMAL PATH AND MINIMAL SPANNING TREES IN RANDOM WEIGHTED NETWORKS 👍 👎
• Minimum spanning trees in networks with varying edge weights 👍 👎
• Approximations for the Random Minimal Spanning Tree with Application to Network Provisioning 👍 👎
• Minimum spanning trees of random geometric graphs with location dependent weights 👍 👎
• A randomly weighted minimum spanning tree with a random cost constraint 👍 👎
• A randomly weighted minimum spanning tree with a random cost constraint 👍 👎

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)