Minimum spanning trees in networks with varying edge weights |
| |
Authors: | Kevin R. Hutson Douglas R. Shier |
| |
Affiliation: | (1) Department of Mathematics Computer Science, Denison University, Granville, Ohio, 43023, U.S.A;(2) Department of Mathematical Sciences, Clemson University, Clemson, South Carolina 29634-0975, USA |
| |
Abstract: | This paper considers the problem of determining minimum spanning trees in networks in which each edge weight can assume a finite number of distinct values. We use the algebraic structure of an underlying Hasse diagram to describe the relationship between different edge-weight realizations of the network, yielding new results on how MSTs change under multiple edge-weight perturbations. We investigate various implementation strategies for updating MSTs in this manner. Computational results are provided for some challenging test networks. |
| |
Keywords: | Cutsets Networks Reliability Sensitivity analysis Spanning trees Stochastic networks |
本文献已被 SpringerLink 等数据库收录! |
|