Рассматривается известная NP-трудная задача нахождения минимального остов-ного k-дерева в простом взвешенном графе. Данную задачу необходимо решать при проектировании надежной телекоммуникационной сети наименьшей стоимости. Предлагается серия эвристических алгоритмов. Определены оценки трудоёмкости алгоритмов, доказана их корректность. Проведён вычислительный эксперимент по сравнению эффективности предложенных алгоритмов, как между собой, так и с известными приближёнными и точными алгоритмами.
Скачать электронную версию публикации
Загружен, раз: 141
- Title Эвристики построения надежной телекоммуникационной сети
- Headline Эвристики построения надежной телекоммуникационной сети
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 7 (Приложение)
- Date:
- DOI
Ключевые слова
spanning k-tree, invulnerable networks, NP-hard, heuristics, остовное k-дерево, надёжная сеть, IFI-сеть, NP-трудность, эвристикиАвторы
Ссылки
Farley A. Networks immune to isolated failures // Networks. 1981. No. 11. P. 255-268.
Rose D. On simple characterizations of k-trees // Discr. Math. 1974. No. 7. P. 317-322.
Prim R. Shortest connection networks and some generalizations // Bell Systems Techn. J. 1957. No. 36. P. 1389-1397.
Bern M. Networks Design Problems: Steiner Trees and Spanning k-Trees. Ph. D. Thesis. University of Berkeley, 1987. 289 p.
Candia A. and Bravo H. A simulated annealing approach for minimum cost isolated failure immune networks // Essays and Surveys in Metaheuristics. 2002. V. 15. P. 169-183.
Beltran H. and Skorin-Kapov D. On minimum cost isolated failure immune network // Telecommunication Systems. 1994. No. 3. P. 183-200.
Эвристики построения надежной телекоммуникационной сети | Прикладная дискретная математика. 2014. № 7 (Приложение).
Скачать полнотекстовую версию
Загружен, раз: 1916