An Efficient Algorithm for Graph Sum Coloring Problem

Please enable javascript in your browser.

Mohammadnejad Daryani, Amin | 2012

712 Viewed

Type of Document: M.Sc. Thesis
Language: Farsi
Document No: 43840 (01)
University: Sharif University of Technology
Department: Industrial Engineering
Advisor(s): Eshghi, Kourosh
Abstract:
Graph sum coloring problem is a special case of graph vertex coloring. Because of its applications in practical areas, especially in scheduling, many researchers have been attracted to it. In recent years, several heuristic and metaheuristic algorithms were applied to sum coloring problem. In this research a heuristic algorithm based on mini-max ant system and simulated annealing metaheuristics is used for graph sum coloring problem. This algorithm is tested on random graphs used in the literature and compared with prior algorithms. Results show that in many cases our proposed algorithm reaches the best known results or improves them
Keywords:
Heuristic Algorithm ; Ant System Algorithm ; Sum Coloring ; Graph Coloring ; Meta Heuristic Algorithm ; Local Search ; Simulated Annealing Method

No TOC