Общая задача синтеза надежных сетей

• Published in: Advances in Astronomy and Space Physics
• Date: 2011
• Main Authors: Шор, Н.З., Шарифов, Ф.А.
• Format: Article
• Language: English
• Published: Головна астрономічна обсерваторія НАН України 2011
• Online Access: https://nasplib.isofts.kiev.ua/handle/123456789/206763
• Journal Title: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Cite this: Общая задача синтеза надежных сетей / Н.З. Шор, Ф.А. Шарифов // Проблемы управления и информатики. — 2006. — № 1-2. — С. 184-202. — Бібліогр.: 32 назв. — рос.

Розглядається важлива для розвитку теорії та практики задача проектування мережі мінімальної вартості, що продовжує функціонувати навіть при виході з ладу окремих її компонент. Кількість обмежень в моделі з потоковими змінними 0 та 1 експоненційно залежить від кількості вузлів; показано, що LP -релаксація цієї задачі NP -складна. Для окремих випадків доведено, що розв’язок відповідної LP -релаксації цієї задачі можна знайти за допомогою поліноміального алгоритму. Запропоновано ефективні алгоритми обчислення верхньої та нижньої границь для двозв’язної задачі Штейнера. Для розв’язання цієї задачі застосовується метод гілок та границь; наведено також результати обчислювальних експериментів. 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.