Kevin R. Hutson

Department of Mathematics and Computer Science

Denison University

Granville, OH 43023

Douglas R. Shier

Department of Mathematical Sciences

Clemson University

Clemson, SC 29634-0975

Abstract: This paper considers the problem of determining the distribution of the weight of a minimum spanning tree (MST) for an undirected network with edge weights that are independently distributed discrete random variables. We use the algebraic structure of an underlying Hasse diagram to describe the relationship between different edge-weight realizations of the stochastic network, yielding new results on how MSTs change under multiple edge-weight perturbations. We investigate various implementation strategies for updating MSTs in this manner and thus deriving the MST weight distribution. Computational results are provided for some challenging stochastic networks.

Key Words: graph theory, networks, reliability, stochastic models