A List based Approach to Solve Graph Coloring Problem
Authors:
- 1 November 2018
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 265-267
Abstract
In this paper we present a list based solution to the graph coloring problem which is simple & efficient. The proposed algorithm may be applied either on dense graph or sparse graph for coloring the node without affecting its complexity. For given an undirected graph G= (V,E) the graph coloring problem consist in assigning a color to each vertex in such a manner that no two adjacent vertex have same color. In most of the algorithms researchers focused to deal the problem by considering only constraints given in the problem. But during coloring of the nodes in the graph, some constraints may generated, which required to be handled explicitly. Our proposed algorithm deals this problem carefully and assigning of colors to vertices will done in such a manner that without generating any other constraints the graph can be colored efficiently.Keywords
This publication has 14 references indexed in Scilit:
- A new DSATUR-based algorithm for exact vertex coloringComputers & Operations Research, 2012
- Coloring graphs by iterated local search traversing feasible and infeasible solutionsDiscrete Applied Mathematics, 2008
- A cutting plane algorithm for graph coloringDiscrete Applied Mathematics, 2008
- A graph coloring model for a feasibility problem in monthly crew scheduling with preferential biddingComputers & Operations Research, 2007
- An exact method for graph coloringComputers & Operations Research, 2006
- A Branch-and-Cut algorithm for graph coloringDiscrete Applied Mathematics, 2006
- Register allocation and spilling via graph coloringACM SIGPLAN Notices, 2004
- On a graph-theoretical model for cyclic register allocationDiscrete Applied Mathematics, 1999
- Improving heuristics for the frequency assignment problemEuropean Journal of Operational Research, 1998
- An introduction to timetablingEuropean Journal of Operational Research, 1985