ЗАГАЛЬНА ЗАДАЧА СИНТЕЗУ НАДІЙНИХ МЕРЕЖ
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...
Gespeichert in:
| Datum: | 2006 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Ukrainian |
| Veröffentlicht: |
V.M. Glushkov Institute of Cybernetics of NAS of Ukraine
2006
|
| Online Zugang: | https://jais.net.ua/index.php/files/article/view/401 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Problems of Control and Informatics |
Institution
Problems of Control and Informatics| Zusammenfassung: | 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. |
|---|