Вісник № 26
Постійне посилання колекціїhttps://repository.kpi.kharkov.ua/handle/KhPI-Press/30153
Переглянути
Документ Новый эвристический алгоритм раскраски графа(НТУ "ХПИ", 2008) Прокопенков, Владимир Филиппович; Кожин, Юрий Николаевич; Малых, Олег НиколаевичВ дискретной математике известны разные алгоритмы раскраски графов: точные, переборные, эвристические. Недостатком точных и переборных алгоритмов является то, что они характеризуются неполиномиальной сложностью от количества вершин в графе. Эвристические требуют меньших затрат времени, но не гарантируют получения оптимального решения. В предлагаемой статье описывается новый эвристический алгоритм раскраски графа, обладающий линейной сложностью. Качество окраски достигается выбираемым порядком обработки вершин.