ON STOCHASTIC SPANNING TREE PROBLEM

This paper considers a generalized version of the stochastic spanning tree problem in which edge costs are random variables and the objectiv e 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 h as been solved polynomially using a parameteric approach. Also, the sa me parametric method without increasing the complexity order has been extended to include the right-hand side also as a decision variable. I n this paper, two different methods are given for solving the generali zed problem. First, a different parametric method better than the earl ier one is given. Then, a method that makes use of the efficient extre me 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 t hat in the worst case the bicriteria method is superior. (C) 1993 by J ohn Wiley & Sons, Inc.