Group 9: Elena Perego, Simon Köhl, Zen Zeps, Deniz Riester, Dan Parii, Iñigo Anguio

Algorithms for the Graph Coloring Problem

This project implements Brute Force, Backtracking, DSatur, Recursive Largest First (RLF), Branch-and-Cut algorithm, Bron Kerbosh, Bipartite Detection algorithms to solve the NP-hard Graph Coloring Problem by computing the exact chromatic number, its upper bound, and its lower bound.

How to run

Please download this repository and navigate into the root folder of this project.

1. Tournament version

• To run the tournament version of our code just type in the command "java -jar Group09.jar %Graph_File%", where "%Graph_File%" needs to be substituted with the path to the graph file on which to run our program, and hit enter.

2. Report version

• To run the report version of our code with verbose output, just type in "java -jar 09-CodeThirdPhase.jar %Graph_File%" and hit enter. (See above for substitution rules on "%Graph_File%").

Note:

To inspect our code, navigate into the corresponding folder ("ReportCode" for the code run when executing "09-CodeThirdPhase.jar" and "TournamentCode" for the code to be used in our tournament version. The only difference between these two folders is the "ReadGraph.java" / "ReadGraphTournament.java" file, which has its only differences in what it prints in the terminal/cmd).