Нахождение максимального разреза гриди алгоритмом
Рассмотрена задача нахождения максимального разреза на графaх. Приводится новая модель задачи в терминах базы полиматроида. Показано, что решение задачи можно найти гриди алгоритмом после определения оптимального линейного упорядочения вершин. Розглянуто задачу знаходження максимального розрізу на г...
Saved in:
| Published in: | Кибернетика и системный анализ |
|---|---|
| Date: | 2018 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2018
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/161430 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Нахождение максимального разреза гриди алгоритмом / Ф.А. Шарифов // Кибернетика и системный анализ. — 2018. — Т. 54, № 5. — С. 61-67. — Бібліогр.: 9 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862727867069104128 |
|---|---|
| author | Шарифов, Ф.А. |
| author_facet | Шарифов, Ф.А. |
| citation_txt | Нахождение максимального разреза гриди алгоритмом / Ф.А. Шарифов // Кибернетика и системный анализ. — 2018. — Т. 54, № 5. — С. 61-67. — Бібліогр.: 9 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| 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.
|
| first_indexed | 2025-12-07T19:05:37Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-161430 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1019-5262 |
| language | Russian |
| last_indexed | 2025-12-07T19:05:37Z |
| publishDate | 2018 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| 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 |
| spellingShingle | Нахождение максимального разреза гриди алгоритмом Шарифов, Ф.А. Системний аналіз |
| title | Нахождение максимального разреза гриди алгоритмом |
| title_alt | Знаходження максимального розрізу гріді алгоритмом Finding maximum cut by the greedy algorithm |
| title_full | Нахождение максимального разреза гриди алгоритмом |
| title_fullStr | Нахождение максимального разреза гриди алгоритмом |
| title_full_unstemmed | Нахождение максимального разреза гриди алгоритмом |
| title_short | Нахождение максимального разреза гриди алгоритмом |
| title_sort | нахождение максимального разреза гриди алгоритмом |
| topic | Системний аналіз |
| topic_facet | Системний аналіз |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/161430 |
| work_keys_str_mv | AT šarifovfa nahoždeniemaksimalʹnogorazrezagridialgoritmom AT šarifovfa znahodžennâmaksimalʹnogorozrízugrídíalgoritmom AT šarifovfa findingmaximumcutbythegreedyalgorithm |