Выходит 12 номеров в год
ISSN Печать: 1064-2315
ISSN Онлайн: 2163-9337
Indexed in
The General Reliability Network Design Problem
Краткое описание
We consider the important practical and theoretical problem of designing communication network with a minimum total cost to operate under condition of certain its components failing. 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 the solution of LP-relaxation problem can be obtained by polynomial algorithm. We propose effective algorithms to compute lower and upper bounds for the two connected Steiner problem. For finding this problem solution we employ the branch and bound algorithm and we also report on some computational results.