Новый эвристический алгоритм раскраски графа

dc.contributor.authorПрокопенков, Владимир Филипповичru
dc.contributor.authorКожин, Юрий Николаевичru
dc.contributor.authorМалых, Олег Николаевичru
dc.date.accessioned2017-06-20T08:22:49Z
dc.date.available2017-06-20T08:22:49Z
dc.date.issued2008
dc.description.abstractВ дискретной математике известны разные алгоритмы раскраски графов: точные, переборные, эвристические. Недостатком точных и переборных алгоритмов является то, что они характеризуются неполиномиальной сложностью от количества вершин в графе. Эвристические требуют меньших затрат времени, но не гарантируют получения оптимального решения. В предлагаемой статье описывается новый эвристический алгоритм раскраски графа, обладающий линейной сложностью. Качество окраски достигается выбираемым порядком обработки вершин.ru
dc.description.abstractThe exact, searching and heuristic algorithms are known in discrete mathematics. Non polynomial computational complexity in relation to graph nodes quantity is the imperfection of exact and searching algorithms. The heuristic algorithms are need smallest time, but optimal solution isn’t guaranteed. This article presents new graph paint heuristic algorithm with linear computational complexity. The paint quality is achieved by selected nodes processing order.en
dc.identifier.citationПрокопенков В. Ф. Новый эвристический алгоритм раскраски графа / В. Ф. Прокопенков, Ю. Н. Кожин, О. Н. Малых // Вестник Нац. техн. ун-та "ХПИ" : сб. науч. тр. Темат. вып. : Системный анализ, управление и информационные технологии. – Харьков : НТУ "ХПИ", 2008. – № 26. – С. 190-194.ru
dc.identifier.urihttps://repository.kpi.kharkov.ua/handle/KhPI-Press/30223
dc.language.isoru
dc.publisherНТУ "ХПИ"ru
dc.subjectcolor counterru
dc.subjectалгоритмru
dc.subjectчисло хроматическоеru
dc.titleНовый эвристический алгоритм раскраски графаru
dc.typeArticleen

Файли

Контейнер файлів

Зараз показуємо 1 - 1 з 1
Ескіз
Назва:
vestnik_KhPI_2008_26_Prokopenkov_Novyiy_evristicheskiy.pdf
Розмір:
198.12 KB
Формат:
Adobe Portable Document Format
Опис:

Ліцензійна угода

Зараз показуємо 1 - 1 з 1
Ескіз недоступний
Назва:
license.txt
Розмір:
11.21 KB
Формат:
Item-specific license agreed upon to submission
Опис: