Fuzzy random bottleneck spanning tree problems using possibility and necessity measures

This paper investigates bottleneck spanning tree problems where each cost attached to the edge in a given graph is represented with a fuzzy random variable. The problem is to find the optimal spanning tree that maximizes a degree of possibility or necessity under some chance constraint. After transforming the problem into the deterministic equivalent one, we introduce the subproblem which has close relations to the deterministic problem. Utilizing fully the relations, we give a polynomial order algorithm for solving the deterministic problem. (C) 2002 Elsevier B.V. All rights reserved.