Heuristics for the multi-level capacitated minimum spanning tree problem |
| |
Authors: | Christos A Pappas Angelos-Christos G Anadiotis Chrysa A Papagianni Iakovos S Venieris |
| |
Institution: | 1. Intelligent Communications and Broadband Networks Laboratory, National Technical University of Athens, Iroon Polytechneiou 9 Str., Zografou, 15773, Athens, Greece 2. Network Management and Optimal Design Laboratory, National Technical University of Athens, Iroon Polytechneiou 9 Str., Zografou, 15773, Athens, Greece
|
| |
Abstract: | The capacitated minimum spanning tree (CMST) problem is fundamental to the design of centralized communication networks. In this paper we consider the multi-level capacitated minimum spanning tree problem, a generalization of the well-known CMST problem. Based on work previously done in the field, three heuristics are presented, addressing unit and non-unit demand cases. The proposed heuristics have been also integrated into a mixed integer programming solver. Evaluation results are presented, for an extensive set of experiments, indicating the improvements that the heuristics bring to the particular problem. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|