Please use this identifier to cite or link to this item: http://repository.kpi.kharkov.ua/handle/KhPI-Press/30223
Title: Новый эвристический алгоритм раскраски графа
Authors: Прокопенков, Владимир Филиппович
Кожин, Юрий Николаевич
Малых, Олег Николаевич
Keywords: color counter; алгоритм; число хроматическое
Issue Date: 2008
Publisher: НТУ "ХПИ"
Citation: Прокопенков В. Ф. Новый эвристический алгоритм раскраски графа / В. Ф. Прокопенков, Ю. Н. Кожин, О. Н. Малых // Вестник Нац. техн. ун-та "ХПИ" : сб. науч. тр. Темат. вып. : Системный анализ, управление и информационные технологии. – Харьков : НТУ "ХПИ", 2008. – № 26. – С. 190-194.
Abstract: В дискретной математике известны разные алгоритмы раскраски графов: точные, переборные, эвристические. Недостатком точных и переборных алгоритмов является то, что они характеризуются неполиномиальной сложностью от количества вершин в графе. Эвристические требуют меньших затрат времени, но не гарантируют получения оптимального решения. В предлагаемой статье описывается новый эвристический алгоритм раскраски графа, обладающий линейной сложностью. Качество окраски достигается выбираемым порядком обработки вершин.
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.
URI: http://repository.kpi.kharkov.ua/handle/KhPI-Press/30223
Appears in Collections:Вісник № 26
Кафедра "Системний аналіз та інформаційно-аналітичні технології"

Files in This Item:
File Description SizeFormat 
vestnik_KhPI_2008_26_Prokopenkov_Novyiy_evristicheskiy.pdf198,12 kBAdobe PDFThumbnail
View/Open
Show full item record  Google Scholar



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.