Нахождение максимального разреза гриди алгоритмом
Рассмотрена задача нахождения максимального разреза на граф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| Zusammenfassung: | Рассмотрена задача нахождения максимального разреза на граф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 |