تجاوز إلى المحتوى الرئيسي
User Image

Amani Ahmed AlAhmadi- أماني أحمد الأحمدي

Lecturer

Faculty

علوم الحاسب والمعلومات
Dareia Campus, Building 6, Third Floor, Office 23
المنشورات
ورقة مؤتمر
2014

Time Efficient Demon Algorithm for Graph Coloring with Search Cut-off Property

Hosny, Amani Al Ahmadi, Taghreed Al Amri, and Manar . 2014

 

The Graph Coloring Problem (GCP) is an important practical problem which belongs to the NP-hard class. It is a constraint satisfaction problem that paints a graph using a minimal number of colors, where any two adjacent vertices should have different colors. Most state-of-the-art metaheuristics methods for the GCP start by one or more infeasible solutions and then attempt to obtain a feasible one. In contrast, this paper proposes a performance competitive Demon Algorithm (DA) that starts with a feasible solution, obtained by a greedy algorithm, and tries to maintain feasibility, while the number of colors used to color the graph is reduced one at a time. The enhancement of performance is related to the way that the DA stops searching once a feasible solution is obtained after each color reduction. The paper spotlights the differences in the performance when applying the same algorithm using Simulated Annealing (SA) as well as Threshold Acceptance (TA) algorithms. Experiments carried out on instances of DIMACS benchmark showed that the proposed DA succeeds to achieve the best known results with very efficient time performance.

موقع المؤتمر
London, UK
اسم المؤتمر
Science and Information Conference 2014
المنظمة الممولة
IEEE, Springer
مزيد من المنشورات