List Colouring of Graphs Using a Genetic Algorithm
The List Colouring Problem (LCP) is an NP-Hard optimization problem in which the goal is to find a proper list colouring of a graph G = (V, E) such that the number of colours used is minimized. This paper deals with the development and implementation of a
- PDF / 359,970 Bytes
- 9 Pages / 439.37 x 666.142 pts Page_size
- 51 Downloads / 194 Views
Abstract The List Colouring Problem (LCP) is an NP-Hard optimization problem in which the goal is to find a proper list colouring of a graph G = (V, E) such that the number of colours used is minimized. This paper deals with the development and implementation of a Genetic Algorithm for the list colouring of graphs. Initial solutions are generated using two heuristics in equal proportion. Experiments have been carried out on randomly generated planar graphs with a list of colours for each vertex. Results for 32 graphs with size varying from 10 to 750 show that the proposed Genetic Algorithm implementation tends towards lower values of the number of colours used. Keywords List colouring
Genetic Algorithm
1 Introduction Let C be a set of colours, and for each v V (G), let L: V(G) ! 2c be a function assigning to each vertex v V(G) a list of colours L(v) C. If Ǝ a function f: V (G) ! C such that f (v) L (v) for all v V (G) and f (u) 6¼ f(v) for uv E (G), then G is said to be L-colourable [1]. In LCP, a vertex colouring of an L-colourable graph G is an assignment of colour to each vertex vi V(G) from its list assignment Li so as to obtain a proper colouring of G with the least number of colours [1]. LCP is an NP-Hard problem [1]. In this paper, a Genetic Algorithm is developed to optimize the number of colours being used. A large number of practical life problems can be formulated as LCP [1, 2]. A. Khandelwal (&) P. Jain G. Saran Department of Mathematics, Dayalbagh Educational Institute, Agra, India e-mail: [email protected] P. Jain e-mail: [email protected] G. Saran e-mail: [email protected] © Springer Nature Singapore Pte Ltd. 2018 S. C. Satapathy et al. (eds.), Smart Computing and Informatics, Smart Innovation, Systems and Technologies 77, https://doi.org/10.1007/978-981-10-5544-7_56
573
574
A. Khandelwal et al.
In 1997, Dimitris and Michael [3] analysed a greedy list colouring algorithm that successfully finds a list colouring of a graph G if no list Lv assigned to vertex v (V (G)) is empty. They have also proved that almost all graphs with n vertices and 1.923 n edges are 3-colourable. Maya and Constantin [4], in 2005, have designed a heuristic for list colouring of graphs. The colour maximally applicable is chosen and is assigned to vertices without violating the requirements of list colouring. The coloured vertices and the colours used are removed, and the same procedure continues till all vertices are coloured.
1.1
Organization
The rest of the paper is organized as follows. Section 1.2 describes LCP. In Sect. 2, heuristics for generating initial population are described. Implementation details of LCP are presented in Sect. 3. Section 4 is devoted to computational experiments, and the results followed by conclusions in Sect. 5.
1.2
Genetic Algorithm for List Colouring Problem
Genetic Algorithm (GA) mimics the process of natural evolution to generate solutions to optimization problems. The basic GA is described in [5], its adaptation to the List Colouring Pro
Data Loading...
