Perbandingan Waktu Eksekusi Algoritma Dsatur dan Algoritma Pewarnaan Heuristik Tabu Search pada Pewarnaan Graf

Abstract

A coloring of graph G is assignment of colors to the vertices of G, one color to each vertex, so that adjacent vertices are assigned distinct colors. If x colors are used, then the coloring is referred to as an x-coloring. If it is possible to find a proper coloring of a graph G, using x colors, G is said to be x-colorable. The chromatic number of a graph G is the smallest integer x for which G is xcolorable, and is denoted by x (G). There are many heuristic methods that can be used to solve graph coloring problem. One of the algorithm can be implemented is tabu seach algorithm.