On the k-coloring problem

On the k-coloring problem

0.00 Avg rating0 Votes
Article ID: iaor19951833
Country: South Korea
Volume: 19
Issue: 3
Start Page Number: 219
End Page Number: 232
Publication Date: Dec 1994
Journal: Journal of the Korean ORMS Society
Authors: ,
Keywords: heuristics
Abstract:

A fixed k-coloring problem is introduced and dealt with by efficient heuristic algorithms. It is shown that the problem can be transformed into the graph partitioning problem. Initial coloring and improving methods are proposed for problems with and without the size restriction. Algorithms Move, LEE and OEE are developed by modifying the Kernighan-Lin’s two way uniform partitioning procedure. The use of global information in the selection of the node and the color set made the proposed algorithms superior to the existing method. The computational result also shows that the superiority does not sacrifice the time demand of the proposed algorithms. [In Korean.]

Reviews

Required fields are marked *. Your email address will not be published.