An efficient complete enumeration method for network design problems and its applications

In many network design problems, the best layout of components is searched considering construction cost and network reliability. Because of #P-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.