Heuristic Methods for Graph Coloring Problems

Author

Andrew LIM, Hong Kong University of Science and Technology
Yi ZHU, Hong Kong University of Science and Technology
Q. LOU, National University of Singapore
Brian RODRIGUES, Singapore Management UniversityFollow

Publication Type

Conference Proceeding Article

Publication Date

2005

Abstract

In this work, the Graph Coloring Problem and its generalizations - the Bandwidth Coloring Problem, the Multicoloring Problem and the Bandwidth Multicoloring Problem - are studied. A Squeaky Wheel Optimization with Tabu Search heuristic is developed and experiments using benchmark geometric test cases show that the algorithm performs well for these problems and achieves results for the Bandwidth Multicoloring Problem which improve on results obtained by other researchers.

Discipline

Operations and Supply Chain Management

Research Areas

Operations Management

Publication

SAC '05: Proceedings of the 2005 ACM Symposium on Applied Computing, Santa Fe, New Mexico, March 13-17

First Page

933

Last Page

939

ISBN

9781581139648

Identifier

10.1145/1066677.1066892

Publisher

ACM

City or Country

Sante Fe, Mexico

Citation

LIM, Andrew; ZHU, Yi; LOU, Q.; and RODRIGUES, Brian. Heuristic Methods for Graph Coloring Problems. (2005). SAC '05: Proceedings of the 2005 ACM Symposium on Applied Computing, Santa Fe, New Mexico, March 13-17. 933-939.
Available at: https://ink.library.smu.edu.sg/lkcsb_research/2386