JOURNAL OF SOFTWARE (JSW)

ISSN : 1796-217X

Volume : 1 Issue : 2 Date : August 2006

**Increasing the Efficiency of Graph Colouring Algorithms with a Representation Based on Vector **

Operations

István Juhos and Jano I. van Hemert

Page(s): 24-33

Full Text: PDF (700 KB)

**Abstract**

We introduce a novel representation for the graph colouring problem, called the Integer Merge

Model, which aims to reduce the time complexity of graph colouring algorithms. Moreover, this

model provides useful information to aid in the creation of heuristics that can make the colouring

process even faster. It also serves as a compact definition for the description of graph colouring

algorithms. To verify the potential of the model, we use it in the complete algorithm DSATUR, and in

two version of an incomplete approximation algorithm; an evolutionary algorithm and the same

evolutionary algorithm extended with guiding heuristics. Both theoretical and empirical results are

provided investigation is performed to show an increase in the efficiency of solving graph colouring

problems. Two problem suites were used for the empirical evidence: a set of practical problem

instances and a set of hard problem instances from the phase transition.

**Index Terms**

graph colouring, representation, node merging, colouring strategies, evolutionary algorithm,

DSATUR

ISSN : 1796-217X

Volume : 1 Issue : 2 Date : August 2006

Operations

Page(s): 24-33

Full Text: PDF (700 KB)

Model, which aims to reduce the time complexity of graph colouring algorithms. Moreover, this

model provides useful information to aid in the creation of heuristics that can make the colouring

process even faster. It also serves as a compact definition for the description of graph colouring

algorithms. To verify the potential of the model, we use it in the complete algorithm DSATUR, and in

two version of an incomplete approximation algorithm; an evolutionary algorithm and the same

evolutionary algorithm extended with guiding heuristics. Both theoretical and empirical results are

provided investigation is performed to show an increase in the efficiency of solving graph colouring

problems. Two problem suites were used for the empirical evidence: a set of practical problem

instances and a set of hard problem instances from the phase transition.

DSATUR