TY - JOUR
AU - Al-Ibrahim, Mohamed
AU - Al-Ibrahim, Naser
AU - Rafique, Yousef
AU - Al-Sumait, Omar
PY - 2016/11/09
Y2 - 2024/05/30
TI - Complementary Graph Coloring
JF - International Journal of Computer (IJC)
JA - IJC
VL - 23
IS - 1
SE - Articles
DO -
UR - https://ijcjournal.org/index.php/InternationalJournalOfComputer/article/view/736
SP - 42-52
AB - <p class="Els-Abstract-text">The objective of the Graph Coloring problem is to color vertices of a graph in such a way that no two vertices that share an edge are assigned the same color. Aircraft Scheduling, Frequency Assignment, register allocation are all real life applications that can be solved using graph coloring. Graph Coloring is a well-known NP-complete problem to the academia in computer science and mathematics. In this paper we use the concept of complementary graphs to come up with a new heuristic for graph coloring. Our results are compared with an exact algorithm and other heuristic algorithms to evaluate our algorithm’s performance. </p>
ER -