A New Clustering Based Algorithm for Solving Graph Coloring Problem

摘要：

Coloring a graph involves labeling each node so that adjacent nodes have different labels. A minimum coloring of a graph is a coloring that uses as few different labels as possible. The problem of coloring graph with the minimum number of colors is well known to be NP-Hard. In this paper, a new clustering based algorithm is presented for the graph coloring problem with the minimum number of colors. The proposed algorithm is evaluated on the DIMACS challenge benchmarks. We compare the results with three other existing coloring algorithms and experimental results on DIMACS graphs Benchmark instances show improvements over existing algorithms for the graph coloring problem.

关键词： Graph Coloring Clustering algorithm

作者: Roohollah Etemadi Alireza Hajieskandar

作者单位: Department of Electrical and computer engineering Islamic Azad University Bonab Branch Bonab. Iran Department of Electrical and computer engineering Islamic Azad University Bonab Branch Bonab, Iran

会议类型: 国际会议

会议名称: 2011 3rd International Conference on Computer and Automation Engineering(ICCAE 2011)(2011年第三届IEEE计算机与自动化工程国际会议)

会议地点: 重庆

会议语种:英文

页码: 154-158

在线出版日期: 2011-01-21（万方平台首次上网日期，不代表论文的发表时间）