Новый эвристический алгоритм раскраски графа - Прокопенков, Владимир Филиппович; Кожин, Юрий Николаевич; Малых, Олег Николаевич (Bulletin of National Technical University "KhPI". Series: System Analysis, Control and Information Technologies, 2017)
В дискретной математике известны разные алгоритмы раскраски графов: точные, переборные, эвристические. Недостатком точных и переборных алгоритмов является то, что они характеризуются неполиномиальной сложностью от количества вершин в графе. Эвристические требуют меньших затрат времени, но не гарантируют получения оптимального решения. В предлагаемой статье описывается новый эвристический алгоритм раскраски графа, обладающий линейной сложностью. Качество окраски достигается выбираемым порядком обработки вершин.