Journal of Applied Mathematics
Volume 2012 (2012), Article ID 364086, 17 pages
Research Article

Risk-Control Approach for a Bottleneck Spanning Tree Problem with the Total Network Reliability under Uncertainty

1Graduate School of Information Science and Technology, Osaka University, 2-1 Yamadaoka, Suita, Osaka 565-0871, Japan
2Graduate School of Engineering, Hiroshima University, 1-4-1 Kagamiyama, Higashi-Hiroshima, Hiroshima 739-8527, Japan
3Department of Mathematical Sciences, Faculty of Science and Engineering, Doshisha University, 1-3 Tatara Miyakodani, Kyotanabe, Kyoto 610-0321, Japan

Received 2 April 2012; Accepted 18 August 2012

Academic Editor: Baocang Ding

Copyright © 2012 Takashi Hasuike et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.


This paper considers a new risk-control and management approach for a bottleneck spanning tree problem under the situation where edge costs in a given network include randomness and reliability. Particularly, this paper focuses on the case that only mean value and variance of edge costs are calculated without assuming a specific random distribution. In order to develop the risk control approach, a confidence interval-based formulation is introduced. Using this interval, as well as minimizing the maximum value of worse edge costs, maximizing the minimum value of robust parameters to edge costs is introduced as objective functions in the risk-control. Furthermore, in order to maintain the constructing spanning tree network entirely, the reliability for each edge is introduced, and maximizing the total reliability of spanning tree is assumed as the third objective function. The proposed model is a multiobjective programming problem, and hence, it is difficult to solve it directly without setting some optimal criterion. Therefore, satisfaction functions for each object and the integrated function are introduced, and the exact solution algorithm is developed by performing deterministic equivalent transformations. A numerical example is provided by comparing our proposed model with previous standard models.