Minimum Graph Coloring Problem

Status: Developing ⚠️

Table of Contents

• Description
• Requirements
• Compilation
• How to run it
• Roadmap
• License

1. Description

The Minimum Graph Coloring is a well-known NP-Hard combinatorial optimization problem that consists on assigning the least number of different colors to the vertices of a graph such that every two adjacent vertices are colored with distinct colors.

This project aims to find the chromatic number of an undirected graph.

Three heuristic algorithms were implemented, one based on Simulated Annealing metaheuristic, along with two exact algorithms.

The DIMACS graphs are used as instance files. Available here and here.

2. Requirements

You should have Java JDK 11 installed on your computer.

3. Compilation

You should open the command line and and then open the directory on which you extracted the project.

Being on NP-Hard directory, you should execute the following code on the command line:

• cd src
• cd Classes
• javac *.java

4. How to run it

Access the directory src through the command line and then type java Classes.Application and execute it.

4.1 Instance File selection

As soon as you run the program, you'll be asked to type the name of aa instance file to compute its chromatic number.

You should write the file name along with ".txt" at the end.

Example: david.txt

4.2 Running exact algorithms

You'll also be asked whether you'd like or not to run the Brute Force and Backtracking exact algorithms.

For those you'd like to run, it is enough to type "yes".

4.3 Setting up Simulated Annealing parameters

Before running the heuristic based on Simulated Annealing, you'll be asked to set the initial temperature (T_0), the iterations per temperature (L) and the cooling rate (alpha).

5. Roadmap

Features to be added and corrected in the future:

• Change the random neighbor method of Simulated Annealing as it has not improved the solution quality.

6. License

MIT licensed.