On stochastic spanning tree problem

✍ Scribed by S. Geetha; K. P. K. Nair

• Publisher: John Wiley and Sons
• Year: 1993
• Tongue: English
• Weight: 443 KB
• Volume: 23
• Category: Article
• ISSN: 0028-3045
• DOI: 10.1002/net.3230230805

✦ Synopsis

This paper considers a generalized version of the stochastic spanning tree problem in which edge costs are random variables and the objective is to find a spectrum of optimal spanning trees satisfying a certain chance constraint whose right-hand side also is treated as a decision variable. A special case of this problem with fixed right-hand side has been solved polynomially using a parameteric approach. Also, the same parametric method without increasing the complexity order has been extended to include the right-hand side also as a decision variable. In this paper, two different methods are given for solving the generalized problem. First, a different parametric method better than the earlier one is given. Then, a method that makes use of the efficient extreme points of the convex hull of the mappings of all the spanning trees in a bicriteria spanning tree problem is presented. But it is shown that in the worst case the bicriteria method is superior. 0 7993 by John Wiley & Sons, Inc. R. C. Prim, Shortest connection networks and some generalizations.