A HEURISTIC ALGORITHM FOR THE LIST COLORING

A HEURISTIC ALGORITHM FOR THE LIST COLORING OF A RANDO GRAPH MAYA SATRATZEMI University of Macedonia, Dept. of Aplied Informatics CONSTANTIN TSOUROS Aristotle University, Faculty of Technology Abstract Let G = (V, E) a graph and L (vi) a set of colors asociated to every node viV. A list coloring of G is an asignment of a color c (v i ) L (vi ) to every node of V so that no two adjacent nodes are asigned the

same color. Significant theoretical research into this special case of the clasic coloring problem started roughly the last decade. In the coresponding literature, algorithms are refered to for a particular clas of graphs, e.g. tres. In this paper a heuristic algorithm is formulated in order to achieve a list coloring to a given random graph G with the smalest posible number of colors, whenever G has such a coloring. A smal numerical example of the presented algorithm is given and the paper is incorporated with a relative computational experiment. Keywords: Heuristic, Algorithm, List coloring, NP-complete 1. INTRODUCTION Graph theory is a convenient mathematical tol, which can be used to model, as visual representations, problems that arise in various scientific fields as wel as in real life practical situations. The 7th Balkan Conference on Operational Research “BACOR 05” Constanta, May 205, Romania One of the most outstanding concepts in graph theory is the notion of graph coloring. The coloring of a graph EVG , se [1,2] is an asignment of colors to its nodes so that no two adjacent nodes have the same color. A coloring of G with k colors is a k-coloring. A subset SV is...

Website: fmi.unibuc.ro | Filesize: -
No of Page(s): 7
Download A HEURISTIC ALGORITHM FOR THE LIST COLORING OF A ....pdf