Эвристики построения надежной телекоммуникационной сети

Рассматривается известная NP-трудная задача нахождения минимального остовного $k$-дерева в простом взвешенном графе. Данную задачу необходимо решать при проектировании надежной телекоммуникационной сети наименьшей стоимости. Предлагается серия эвристических алгоритмов. Определены оценки трудоёмкости алгоритмов, доказана их корректность. Проведён вычислительный эксперимент по сравнению эффективности предложенных алгоритмов, как между собой, так и с известными приближёнными и точными алгоритмами.