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.