Общая задача синтеза надежных сетей
Розглядається важлива для розвитку теорії та практики задача проектування мережі мінімальної вартості, що продовжує функціонувати навіть при виході з ладу окремих її компонент. Кількість обмежень в моделі з потоковими змінними 0 та 1 експоненційно залежить від кількості вузлів; показано, що LP -ре...
Gespeichert in:
| Veröffentlicht in: | Advances in Astronomy and Space Physics |
|---|---|
| Datum: | 2011 |
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Englisch |
| Veröffentlicht: |
Головна астрономічна обсерваторія НАН України
2011
|
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/206763 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Общая задача синтеза надежных сетей / Н.З. Шор, Ф.А. Шарифов // Проблемы управления и информатики. — 2006. — № 1-2. — С. 184-202. — Бібліогр.: 32 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862530728298807296 |
|---|---|
| author | Шор, Н.З. Шарифов, Ф.А. |
| author_facet | Шор, Н.З. Шарифов, Ф.А. |
| citation_txt | Общая задача синтеза надежных сетей / Н.З. Шор, Ф.А. Шарифов // Проблемы управления и информатики. — 2006. — № 1-2. — С. 184-202. — Бібліогр.: 32 назв. — рос. |
| collection | DSpace DC |
| container_title | Advances in Astronomy and Space Physics |
| description | Розглядається важлива для розвитку теорії та практики задача проектування мережі мінімальної вартості, що продовжує функціонувати навіть при виході з ладу окремих її компонент. Кількість обмежень в моделі з потоковими змінними 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.
|
| first_indexed | 2025-11-24T03:11:22Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-206763 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 2227-1481 |
| language | English |
| last_indexed | 2025-11-24T03:11:22Z |
| publishDate | 2011 |
| publisher | Головна астрономічна обсерваторія НАН України |
| record_format | dspace |
| spelling | Шор, Н.З. Шарифов, Ф.А. 2025-09-22T09:00:46Z 2011 Общая задача синтеза надежных сетей / Н.З. Шор, Ф.А. Шарифов // Проблемы управления и информатики. — 2006. — № 1-2. — С. 184-202. — Бібліогр.: 32 назв. — рос. 2227-1481 https://nasplib.isofts.kiev.ua/handle/123456789/206763 519.8 Розглядається важлива для розвитку теорії та практики задача проектування мережі мінімальної вартості, що продовжує функціонувати навіть при виході з ладу окремих її компонент. Кількість обмежень в моделі з потоковими змінними 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. en Головна астрономічна обсерваторія НАН України Advances in Astronomy and Space Physics Общая задача синтеза надежных сетей Загальна задача синтезу надійних мереж General Reliability Problems in Network Design Article published earlier |
| spellingShingle | Общая задача синтеза надежных сетей Шор, Н.З. Шарифов, Ф.А. |
| title | Общая задача синтеза надежных сетей |
| title_alt | Загальна задача синтезу надійних мереж General Reliability Problems in Network Design |
| title_full | Общая задача синтеза надежных сетей |
| title_fullStr | Общая задача синтеза надежных сетей |
| title_full_unstemmed | Общая задача синтеза надежных сетей |
| title_short | Общая задача синтеза надежных сетей |
| title_sort | общая задача синтеза надежных сетей |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/206763 |
| work_keys_str_mv | AT šornz obŝaâzadačasintezanadežnyhsetei AT šarifovfa obŝaâzadačasintezanadežnyhsetei AT šornz zagalʹnazadačasintezunadíinihmerež AT šarifovfa zagalʹnazadačasintezunadíinihmerež AT šornz generalreliabilityproblemsinnetworkdesign AT šarifovfa generalreliabilityproblemsinnetworkdesign |