a) (40pts) Design & Improve the AFIT graphprogram for the MIS algorithm.
“Educational Objective: develop an understanding and ability to use the mapping PD (MIS) into AD (gs-dfs/bt) via our top-down design process using Christofides’ MIS algorithm design and implementation from our gs-dfs/bt algorithm specification.” “A software engineer in a closet should now understand the total development from PD/AD integration to pseudo code to code step by step with additional heuristics.”
a.1 (30 points) Incorporate at least the ordering heuristic and the pivoting heuristic** {Andrade, Christofides Bron Kerbisch), Pelillo, …} into the graphprogram MIS by explicitly following our top down PD/AD search element design approach. Show this PD/AD design explicitly integrating step-by-step these creative new heuristics top-down into functional pseudo code. Extend the use of the standard search elements into the given graphprogram code as well as the step notation from the new pseudo code to C++ code with your new heuristics.
OR
Develop the PD/AD design using the ordering and pivoting heuristics for a MIS/Clique algorithm implemented in a different programming language. Of course, include standard search elements throughout the new heuristic design development as appropriate (including implementation).
a.2 (10 points) Test and compare MIS results with/without Heuristics over some relatively small, medium and large PD graphs (From Problem 3 and/or DIMACS,BHOSLIB, …). Consider planer, non-planer, perfect, circle, bipartite, permutation, and chordal graphs? For medium PD graph size, generate search graph.
Report: Discuss the above top-down design, implementation, and
testing efforts concisely! (for testing follow Barr,Talbi1.7)
*consider an ordering of the nodes for selection based upon
number of connections (max, min) in an attempt to find the maximum
independent set. “Heuristic impact?” [complexity?]
** Add an algorithm to implement Christofides Equation 3.9, page 34. This is defined as “pivoting” in some descriptions of the BK algorithm (see Wikipedia and other references). This additional heuristic as stated by Christofides can force the backtracking set earlier. “Heuristic impact?” [complexity?]
