A method for the minimum coloring problem using genetic algorithms
This paper presents a method to solve the graph coloring problem for arbitrary graphs using genetic algorithms. The graph coloring problem, an NP-hard problem, has important applications in many areas including time tabling and scheduling, frequency assignment, and reg ister allocation. The algorith...
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | conferenceObject |
| Published: |
2006
|
| Online Access: | http://hdl.handle.net/10725/7631 http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php http://www.actapress.com/PaperInfo.aspx?PaperID=26827&reason=500 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | This paper presents a method to solve the graph coloring problem for arbitrary graphs using genetic algorithms. The graph coloring problem, an NP-hard problem, has important applications in many areas including time tabling and scheduling, frequency assignment, and reg ister allocation. The algorithm was implemented and tested on various set of instances including large DIMACS challenge benchmark graphs, all yielding favorable results. |
|---|