Description
- (5 pts) Talbi, Problem 1.4 (show for MIS and Clique problems only)
- (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++/ 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:
- Bron-Kerbosch Algorithm, Wikipedia (Checkout Wiki References) https://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm
- BHOSLIB, DIMACS, MIS/Clique Benchmark sets, Bibliography https://iridia.ulb.ac.be/~fmascia/maximum_clique/BHOSLIB-benchmark
- Floudas and Pardalos, (eds.) Encyclopedia of Optimization, p. 411, Kluwer, 2009
- Wikipedia, Software Testing, https://en.wikipedia.org/wiki/Software_testing
- Barr, et al, Guidelines for Designing and Reporting on Computational Experiments with heuristic Methods, 2001 “Great Reference!!”
- https://www.google.com/?gws rd=ssl#q=comparison+of+CLIQUE+algorithms