ЗАГАЛЬНА ЗАДАЧА СИНТЕЗУ НАДІЙНИХ МЕРЕЖ
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...
Saved in:
| Date: | 2006 |
|---|---|
| Main Authors: | , |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
V.M. Glushkov Institute of Cybernetics of NAS of Ukraine
2006
|
| Online Access: | https://jais.net.ua/index.php/files/article/view/401 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Problems of Control and Informatics |
Institution
Problems of Control and Informatics| Summary: | 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. |
|---|