Approximations for the Random Minimal Spanning Tree with Application to Network Provisioning

Anjani Jain and John W. Mamer
Additional contact information
Anjani Jain: University of Pennsylvania, Philadelphia, Pennsylvania
John W. Mamer: University of California, Los Angeles, California

Operations Research, 1988, vol. 36, issue 4, 575-584

Abstract: This paper considers the problem of determining the mean and distribution of the length of a minimal spanning tree (MST) on an undirected graph whose arc lengths are independently distributed random variables. We obtain bounds and approximations for the MST length and show that our upper bound is much tighter than the naive bound obtained by computing the MST length of the deterministic graph with the respective means as arc lengths. We analyze the asymptotic properties of our approximations and establish conditions under which our bounds are asymptotically optimal. We apply these results to a network provisioning problem and show that the relative error induced by using our approximations tends to zero as the graph grows large.

Keywords: facilities/equipment planning: network planning; networks/graphs; stochastic: random minimal spanning trees; tree algorithms: approximations to MSTs (search for similar items in EconPapers)
Date: 1988
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.36.4.575 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:36:y:1988:i:4:p:575-584

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().