Heuristics for Synthesizing Robust Networks with a Diameter Constraint Academic Article uri icon


  • Robustness of a network in the presence of node or link failures plays an important role in the design of the network. A key factor that quantifies this robustness is the algebraic connectivity of the network. In this paper, the authors address the problem of finding a network that maximizes the algebraic connectivity of the network while ensuring that the length of the shortest path joining any two nodes in the network is within a given bound. This paper presents k-opt and tabu search heuristics for finding feasible solutions for this network synthesis problem. Computational results are also presented to corroborate the performance of the proposed algorithms. © 2014 Harsha Nagarajan et al.

author list (cited authors)

  • Nagarajan, H., Wei, P., Rathinam, S., & Sun, D.

citation count

  • 3

publication date

  • January 2014