1. (5 pts) Talbi, Problem 1.4 (show for MIS and Clique problems only)
2. (20pts) Test and evaluate the AFIT graphprogram* for MIS examples that are small, medium and large graph applications (planar & non-planar). Present search tree for medium size application; note that graph program generates required data. Use at least 8 graphs. Utilize appropriate reporting approaches (Barr,Talbi:Section 1.7).
* (on the L: drive under the CSCE686/NPC Problems/MIS_Clique/MIS Software/MIS_C++/ directory. MIS_VC software can also be employed. Software written for Christofides algorithms. Observe that you need to execute VMware in order to interface to the AFIT network and the L: drive. This and other software is to be stored on the AFIT network L: drive because of size.)
References:
1) Bron-Kerbosch Algorithm, Wikipedia (Checkout Wiki References) http://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm
2) BHOSLIB, DIMACS, MIS/Clique Benchmark sets, Bibliography http://iridia.ulb.ac.be/~fmascia/maximum_clique/BHOSLIB-benchmark
3) Floudas and Pardalos, (eds.) Encyclopedia of Optimization, p. 411, Kluwer, 2009
4) Wikipedia, Software Testing, http://en.wikipedia.org/wiki/Software_testing
5) Barr, et al, Guidelines for Designing and Reporting on Computational Experiments with heuristic Methods, 2001 “Great Reference!!”
6) https://www.google.com/?gws rd=ssl#q=comparison+of+CLIQUE+algorithms
