Article ID: | iaor20031599 |
Country: | Japan |
Volume: | 45 |
Issue: | 3 |
Start Page Number: | 299 |
End Page Number: | 316 |
Publication Date: | Sep 2002 |
Journal: | Journal of the Operations Research Society of Japan |
Authors: | Ishii Hiroaki, Shinmori Shuichi, Koide Takeshi |
Keywords: | design, combinatorial analysis, networks |
In many network design problems, the best layout of components is searched considering construction cost and network reliability. Because of NP-completeness for computation of network reliability, most algorithms for the problems find approximate solutions. In this paper, we propose a complete enumeration method for the network design problems, which becomes a basis of exact algorithms. The detection of isomorphic networks appeared in the process of computation can reduce computational time compared with simple complete enumerations. We also discuss applications of the algorithm to other kinds of network design problems.