Новый эвристический алгоритм раскраски графа
Вантажиться...
Дата
2008
ORCID
DOI
Науковий ступінь
Рівень дисертації
Шифр та назва спеціальності
Рада захисту
Установа захисту
Науковий керівник
Члени комітету
Видавець
НТУ "ХПИ"
Анотація
В дискретной математике известны разные алгоритмы раскраски графов: точные, переборные, эвристические. Недостатком точных и переборных алгоритмов является то, что они характеризуются неполиномиальной сложностью от количества вершин в графе. Эвристические требуют меньших затрат времени, но не гарантируют получения оптимального решения. В предлагаемой статье описывается новый эвристический алгоритм раскраски графа, обладающий линейной сложностью. Качество окраски достигается выбираемым порядком обработки вершин.
The 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.
The 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.
Опис
Ключові слова
color counter, алгоритм, число хроматическое
Бібліографічний опис
Прокопенков В. Ф. Новый эвристический алгоритм раскраски графа / В. Ф. Прокопенков, Ю. Н. Кожин, О. Н. Малых // Вестник Нац. техн. ун-та "ХПИ" : сб. науч. тр. Темат. вып. : Системный анализ, управление и информационные технологии. – Харьков : НТУ "ХПИ", 2008. – № 26. – С. 190-194.