Perbandingan Algoritma Pewarnaan LDO, SDO, dan IDO pada Graf Sederhana

Abstract

Abstract – Vertex colouring is coloring graph vertex such that two neighbor vertexs have different colors. The main purpose of colouring is to get minimum number of colors which is called chromatic number. In the application of graph coloring, which is the minimum number of colors means minimizing the amount of resources such as space and time in solving a problem. To perform the necessary vertex a coloring tool is an algorithm that will govern how the coloring process on a graph. The sequence of the color on a vertex can affect many colors needed to color all vertexs of the graph. There are three algorithms that can be used to perform the coloring vertex by vertex for the election to be colored, the algorithm LDO, SDO, and IDO. After testing in a few simple graphs, it is concluded that none amongst algorithm LDO, SDO, and IDO which always produces the minimum number of colors.

Keywords – Vertex colouring, Chromatic number, LDO algorithm, SDO algorithm, IDO algorithm