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

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

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

• A note on two problems in connexion with graphs
• Title not available (Why is that?)
• 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 (17)

• The expected complexity of Prim's minimum spanning tree algorithm
• Note on the structure of Kruskal's algorithm
• Successive minimum spanning trees
• Geometry of minimum spanning trees on scale-free networks
• Minimum spanning trees in networks with varying edge weights
• Invasion percolation on the Poisson-weighted infinite tree
• Bounding Distributions for the Weight of a Minimum Spanning Tree in Stochastic Networks
• Minimal spanning trees in undirected networks with exponentially distributed arc weights
• Multisource invasion percolation on the complete graph
• On the value of a random minimum weight Steiner tree
• 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)
• GHS algorithm on a graph with random weights
• On the probabilistic min spanning tree problem
• Approximations for the Random Minimal Spanning Tree with Application to Network Provisioning
• Critical random graphs and the structure of a minimum spanning tree

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)