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

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Nov 01, 1986
Accession Number
ADA204656

Entities

People

  • Anjani Jain
  • John W. Mamer

Organizations

  • University of California, Los Angeles

Tags

Communities of Interest

  • C4I

DTIC Thesaurus Topics

  • Accuracy
  • Algorithms
  • Combinatorial Analysis
  • Convergence
  • Data Science
  • Distribution Functions
  • Graph Theory
  • Information Science
  • Monte Carlo Method
  • New Jersey
  • New York
  • Normal Distribution
  • Optimization
  • Order Statistics
  • Probability
  • Probability Distributions
  • Random Variables

Readers

  • Graph Algorithms and Convex Optimization.
  • Statistical inference.