Задача нахождения непересекающихся и несовпадающих циклов на сети
Vernadsky National Library of Ukraine
Переглянути архів Інформація| Поле | Співвідношення | |
| Title |
Задача нахождения непересекающихся и несовпадающих циклов на сети
|
|
| Creator |
Шарифов, Ф.А.
|
|
| Description |
We study a minimum cost node and arc-disjoint cycles problem on a directed graph. It is shown that the problem is equivalent to the minimum cost disjoint matchings problem on complete bipartite graph. In particular case, for which weights of arcs are special, then the considered problem is reduced to minimum cost flow problem. Some interesting properties of LP-relaxation problem are proved and it is noted that namely these properties are on bases for polynomial algorithm to solve the problem.
|
|
| Date |
2015-07-16T15:18:55Z
2015-07-16T15:18:55Z 2003 |
|
| Type |
Article
|
|
| Identifier |
Задача нахождения непересекающихся и несовпадающих циклов на сети / Ф.А. Шарифов // Теорія оптимальних рішень: Зб. наук. пр. — 2003. — № 2. — С. 155-161. — Бібліогр.: 8 назв. — рос.
XXXX-0013 http://dspace.nbuv.gov.ua/handle/123456789/84868 519.8 |
|
| Language |
ru
|
|
| Relation |
Теорія оптимальних рішень
|
|
| Publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України
|
|