Efficient Method of Network Design Using Maximum-Reliability Network Construction

Daichi ENOMOTO  Xiao XIAO  Natsumi TAKAHASHI  Hisashi YAMAMOTO  

A - Abstracts of IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences (Japanese Edition)   Vol.J101-A   No.7   pp.178-188
Publication Date: 2018/07/01
Online ISSN: 1881-0195
Type of Manuscript: PAPER
network reliability,  maximum all-terminal reliability,  conditioned cost-minimization network design problem,  algorithm improvement,  

Full Text(in Japanese): PDF(616.8KB)
>>Buy this Article

In this paper, we aim to reduce the computation load of the solution algorithm of a classical all-terminal reliability conditioned cost-minimization network design problem. We propose an efficient method of deriving the maximum all-terminal reliability of the network with n nodes and e edges. The efficiency of the existing solution algorithm is improved by applying the derived polynomial equations to the calculation of the bare minimum number of edges to start the search of solution. It is confirmed in the experiments that our proposal possesses better performance than the existing solution algorithm.