ЗАГАЛЬНА ЗАДАЧА СИНТЕЗУ НАДІЙНИХ МЕРЕЖ
We consider the important practical and theoretical problem of designing communications network with a minimum total cost under condition that an optimal network must survive with respect to failures of certain its components. The model with 0, 1 — flow variables contains a number of constraints tha...
Збережено в:
| Дата: | 2006 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Ukrainian |
| Опубліковано: |
V.M. Glushkov Institute of Cybernetics of NAS of Ukraine
2006
|
| Онлайн доступ: | https://jais.net.ua/index.php/files/article/view/401 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Problems of Control and Informatics |
Репозитарії
Problems of Control and Informatics| Резюме: | We consider the important practical and theoretical problem of designing communications network with a minimum total cost under condition that an optimal network must survive with respect to failures of certain its components. The model with 0, 1 — flow variables contains a number of constraints that is exponential in the number of nodes and we show that its LP-relaxation is NP-complete problem. For some particular cases, we prove that a solution of LP-relaxation problem can be found by polynomial time algorithm. We propose effective algorithms to compute lower and upper bounds for the two connected Steiner problem. For finding a solution of this problem we implement the branch and bound algorithm and we also report on some computational results. |
|---|