Final Project
CSC 422/522, Fall 2014
Dominating Set Challenge- Heuristic Algorithm

Due date: Tues. Dec. 9 by 11:55pm.
Late deadline: Tues. Dec. 16 at 11:55pm with a 10% late penalty.

The goal is to design a fast C or C++ heuristic for the dominating set problem. The program takes as input a sequence of graphs, and finds a small (but not necessarily minimum) dominating set for each one.

The programming specifications are the same as for the exact algorithm submission. But there is a new code for the output. To print a dominating set:
First print either 0 or 1 or 2 where:
0 means that the dominating set is the best found so far, and
1 means that the dominating set is a minimum dominating set for the graph,
and 2 means the algorithm is terminating with a dominating set but it not able to ascertain that it is a minimum dominating set.
The computation for each graph should terminate with either 1 or 2.

Marking Scheme

For CSC 422 students, this project is for bonus marks. For CSC 522 students, this project is worth 10% of the final mark.

The marking scheme:

1. [5] Modular program design.
2. [5] Meaningful variable names.
3. [5] Lots of comments.
4. [5] Efficient application of chosen data structures.
5. [10] Creative tactics applied in order to find small dominating sets. Simple solutions are fine as long as they lead to quality solutions.
6. [40] Correctness.
7. [10] Quality of dominating sets found.
8. [20] Paper describing algorithm.