The goal of this class project is to investigate and evaluate heuristic algorithms for the minimum dominating set problem. Your final submissions will be evaluated for both correctness and quality.
You may submit code that you have previously submitted. Or you could develop a better algorithm.
The specifications are the same as for project submission 1.
All students should submit a program under:
Final submission F1: Your creative algorithm
All students have the option to also submit a program under:
Final submission F2: A published approach
F1 is required for all students. The comments for F1 should explain your data structures and tell me what your algorithm is doing.
F2 is required for CSC 520, and if CSC 425 students include a published heuristic in the final submission, then the grade will replace your lowest assignment score. The approach for F2 could be published in conference proceedings, a journal or a book. Please feel free to modify settings (such as the Tabu list size for Tabu search, or the cooling schedule for simulated annealing) to fine tune it for our input graphs. The comments should reference the place that the algorithm was published and describe the algorithm in pseudocode.