Нахождение максимального разреза гриди алгоритмом
Рассмотрена задача нахождения максимального разреза на графaх. Приводится новая модель задачи в терминах базы полиматроида. Показано, что решение задачи можно найти гриди алгоритмом после определения оптимального линейного упорядочения вершин. Розглянуто задачу знаходження максимального розрізу на г...
Gespeichert in:
| Veröffentlicht in: | Кибернетика и системный анализ |
|---|---|
| Datum: | 2018 |
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2018
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/161430 |
| 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: | Нахождение максимального разреза гриди алгоритмом / Ф.А. Шарифов // Кибернетика и системный анализ. — 2018. — Т. 54, № 5. — С. 61-67. — Бібліогр.: 9 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-161430 |
|---|---|
| record_format |
dspace |
| spelling |
Шарифов, Ф.А. 2019-12-08T17:34:22Z 2019-12-08T17:34:22Z 2018 Нахождение максимального разреза гриди алгоритмом / Ф.А. Шарифов // Кибернетика и системный анализ. — 2018. — Т. 54, № 5. — С. 61-67. — Бібліогр.: 9 назв. — рос. 1019-5262 https://nasplib.isofts.kiev.ua/handle/123456789/161430 519.8 Рассмотрена задача нахождения максимального разреза на графaх. Приводится новая модель задачи в терминах базы полиматроида. Показано, что решение задачи можно найти гриди алгоритмом после определения оптимального линейного упорядочения вершин. Розглянуто задачу знаходження максимального розрізу на графах. Наведено нову модель задачі в термінах бази поліматроїда. Показано, що розв'язок задачі можна знайти гріді алгоритмом після того, як визначено оптимальне лінійне впорядкування вершин. The paper considers the problem of finding the maximum cut on graphs. A new model of the problem is given in terms of the base of polymatroid. It is shown that the problem solution can be found by the greedy algorithm after the optimal linear ordering of the vertices has been determined. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Системний аналіз Нахождение максимального разреза гриди алгоритмом Знаходження максимального розрізу гріді алгоритмом Finding maximum cut by the greedy algorithm Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Нахождение максимального разреза гриди алгоритмом |
| spellingShingle |
Нахождение максимального разреза гриди алгоритмом Шарифов, Ф.А. Системний аналіз |
| title_short |
Нахождение максимального разреза гриди алгоритмом |
| title_full |
Нахождение максимального разреза гриди алгоритмом |
| title_fullStr |
Нахождение максимального разреза гриди алгоритмом |
| title_full_unstemmed |
Нахождение максимального разреза гриди алгоритмом |
| title_sort |
нахождение максимального разреза гриди алгоритмом |
| author |
Шарифов, Ф.А. |
| author_facet |
Шарифов, Ф.А. |
| topic |
Системний аналіз |
| topic_facet |
Системний аналіз |
| publishDate |
2018 |
| language |
Russian |
| container_title |
Кибернетика и системный анализ |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Знаходження максимального розрізу гріді алгоритмом Finding maximum cut by the greedy algorithm |
| description |
Рассмотрена задача нахождения максимального разреза на графaх. Приводится новая модель задачи в терминах базы полиматроида. Показано, что решение задачи можно найти гриди алгоритмом после определения оптимального линейного упорядочения вершин.
Розглянуто задачу знаходження максимального розрізу на графах. Наведено нову модель задачі в термінах бази поліматроїда. Показано, що розв'язок задачі можна знайти гріді алгоритмом після того, як визначено оптимальне лінійне впорядкування вершин.
The paper considers the problem of finding the maximum cut on graphs. A new model of the problem is given in terms of the base of polymatroid. It is shown that the problem solution can be found by the greedy algorithm after the optimal linear ordering of the vertices has been determined.
|
| issn |
1019-5262 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/161430 |
| citation_txt |
Нахождение максимального разреза гриди алгоритмом / Ф.А. Шарифов // Кибернетика и системный анализ. — 2018. — Т. 54, № 5. — С. 61-67. — Бібліогр.: 9 назв. — рос. |
| work_keys_str_mv |
AT šarifovfa nahoždeniemaksimalʹnogorazrezagridialgoritmom AT šarifovfa znahodžennâmaksimalʹnogorozrízugrídíalgoritmom AT šarifovfa findingmaximumcutbythegreedyalgorithm |
| first_indexed |
2025-12-07T19:05:37Z |
| last_indexed |
2025-12-07T19:05:37Z |
| _version_ |
1850877503452741632 |