Search Difficulty of Two-Connected Ring-based Topological Network Designs

Ring-based network design problems have many important applications, especially in the fields of logistics and telecommunications. This paper focuses on the recently proposed two-connected network with bounded rings problem. We investigate the search difficulty of both the Euclidean edge and unit edge length ring size bounds flavors of this problem by performing an information-theoretic fitness landscape analysis for several instances of the problem. Our results further confirm the hypothesis that the unit edge length version of the problem is indeed more difficult. The investigation also further reveals that smaller sized ring bounds lead to harder problems for Euclidean edge lengths. However, for unit edge lengths we did not establish such a relationship