• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Article

Heuristics for the Design of Reliable Networks with k-Tree Topology

International Journal of Artificial Intelligence. 2015. Vol. 13. No. 1. P. 165-183.
Shangin R. E., Pardalos P. M., Panyukov A. V.

In this paper we consider the NP-complete problem of finding a spanning k-tree of minimum weight in a complete weighted graph. This problem has a number of applications in designing reliable backbone telecommunication networks. We propose effective algorithms based on a greedy strategy and several variable neighborhood search metaheuristics. We also develop an integer linear programming model for calculating a lower bound. Preliminary numerical experiments using random and real-word data sets are reported to show the effectiveness of our approach. In addition, we compare our approach with known metaheuristics.