Stochastic bottleneck spanning tree problem

Abstract This paper considers a stochastic version of bottleneck spanning tree problem in which edge costs are random variables. The problem is to find an optimal spanning tree under the chance constraint with respect to bottleneck (maximum cost) edge of spanning tree. The problem is first transformed into a deterministic equivalent problem. Then its subproblem is introduced and a close relation between these problems is clarified. Finally, based on the relation, an algorithm which finds an optimal spanning tree of the original problem in a polynomial order of its problem size is proposed.