ЗАГАЛЬНА ЗАДАЧА СИНТЕЗУ НАДІЙНИХ МЕРЕЖ

ЗАГАЛЬНА ЗАДАЧА СИНТЕЗУ НАДІЙНИХ МЕРЕЖ

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...

Full description

Saved in:
Bibliographic Details
Date:2006
Main Authors: Shor, N.Z., Sharifov , F.A.
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
id oai:ojs2.jais.net.ua:article-401
record_format ojs
spelling oai:ojs2.jais.net.ua:article-4012024-10-23T17:48:36Z THE GENERAL RELIABILITY NETWORK DESIGN PROBLEMS ЗАГАЛЬНА ЗАДАЧА СИНТЕЗУ НАДІЙНИХ МЕРЕЖ Shor, N.Z. Sharifov , F.A. 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. Розглядається важлива для розвитку теорії та практики задача проектування мережі мінімальної вартості, що продовжує функціонувати навіть при виході з ладу окремих її компонент. Кількість обмежень в моделі з потоковими змінними 0 та 1 експоненційно залежить від кількості вузлів; показано, що LP-ре­лаксація цієї задачі NP-складна. Для окремих випадків доведено, що розв’язок відповідної LP-релаксації цієї задачі можна знайти за допомогою поліноміального алгоритму. Запропоновано ефективні алгоритми обчислення верхньої та нижньої границь для двозв’язної задачі Штейнера. Для розв’язання цієї задачі застосовується метод гілок та границь; наведено також результати обчислю-валь­них експериментів. V.M. Glushkov Institute of Cybernetics of NAS of Ukraine 2006-03-20 Article Article application/pdf https://jais.net.ua/index.php/files/article/view/401 Міжнародний науково-технічний журнал "Проблеми керування та інформатики"; Том 51 № 1-2 (2006): Міжнародний науково-технічний журнал "Проблеми керування та інформатики"; 184-202 International Scientific Technical Journal "Problems of Control and Informatics; Том 51 № 1-2 (2006): International Scientific and Technical Journal "PROBLEMS OF CONTROL AND INFORMATICS"; 184-202 International Scientific Technical Journal "Problems of Control and Informatics"; Vol. 51 No. 1-2 (2006): International Scientific and Technical Journal "PROBLEMS OF CONTROL AND INFORMATICS"; 184-202 2786-6505 2786-6491 uk https://jais.net.ua/index.php/files/article/view/401/475 https://creativecommons.org/licenses/by-nc-nd/4.0
institution Problems of Control and Informatics
baseUrl_str
datestamp_date 2024-10-23T17:48:36Z
collection OJS
language Ukrainian
format Article
author Shor, N.Z.
Sharifov , F.A.
spellingShingle Shor, N.Z.
Sharifov , F.A.
ЗАГАЛЬНА ЗАДАЧА СИНТЕЗУ НАДІЙНИХ МЕРЕЖ
author_facet Shor, N.Z.
Sharifov , F.A.
author_sort Shor, N.Z.
title ЗАГАЛЬНА ЗАДАЧА СИНТЕЗУ НАДІЙНИХ МЕРЕЖ
title_short ЗАГАЛЬНА ЗАДАЧА СИНТЕЗУ НАДІЙНИХ МЕРЕЖ
title_full ЗАГАЛЬНА ЗАДАЧА СИНТЕЗУ НАДІЙНИХ МЕРЕЖ
title_fullStr ЗАГАЛЬНА ЗАДАЧА СИНТЕЗУ НАДІЙНИХ МЕРЕЖ
title_full_unstemmed ЗАГАЛЬНА ЗАДАЧА СИНТЕЗУ НАДІЙНИХ МЕРЕЖ
title_sort загальна задача синтезу надійних мереж
title_alt THE GENERAL RELIABILITY NETWORK DESIGN PROBLEMS
description 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.
publisher V.M. Glushkov Institute of Cybernetics of NAS of Ukraine
publishDate 2006
url https://jais.net.ua/index.php/files/article/view/401
work_keys_str_mv AT shornz thegeneralreliabilitynetworkdesignproblems
AT sharifovfa thegeneralreliabilitynetworkdesignproblems
AT shornz zagalʹnazadačasintezunadíjnihmerež
AT sharifovfa zagalʹnazadačasintezunadíjnihmerež
AT shornz generalreliabilitynetworkdesignproblems
AT sharifovfa generalreliabilitynetworkdesignproblems
first_indexed 2025-10-30T02:49:07Z
last_indexed 2025-10-30T02:49:07Z
_version_ 1847373382459326464

Similar Items