CSE - 7350 - Southern Methodist University
This was an individual class project which implements all the algorithm learnt in class of algorithm engineering taking into consideration the time & space complexity of the project.
In this project you are asked to implement an algorithm for determining a coloring, terminal clique, and a selection of bipartite subgraphs that are produced by an algorithm for graph coloring in a random geometric Graph (RGG). These results model a wireless sensor network (WSN) with each bipartite subgraph providing a communication backbone. We split the project into 3 parts on purpose in order to help students arranging time properly to complete the term project within the semester, so part II and part III are expansions from part I. Part III would be the final complete report of the whole project. You are first asked in Part I to prepare several RGG’s as a randomized benchmark set. RGG’s on the plane (unit square), RGG's on a disk (unit circle) and RGG’s on the globe (unit sphere) model WSN’s on geographic regions. In Part I you are further asked to output your graph as an adjacency list. This becomes the input for Part II. In Part II, you are asked to accept an adjacency list as input and implement the smallest-last coloring algorithm for vertex coloring and terminal clique identification in the RGG’s specified by the input. The coloring algorithm is to be applied to the randomized benchmark sets of Part I and is also to be applied to several original graphs you specifically create to exhibit the strengths and weaknesses of the coloring and clique determination algorithms including a few graphs of considerably larger RGG’s. Regarding algorithm efficiency you are asked to verify the running time bound for each algorithm you implement in Part I and Part II with extra credit if you are able to achieve linear time (Q (|V|+|E|)) implementation. You are asked to document your implementations in the form of a report to a technical manager with substantial use of graphic display of results again with extra credit for interfacing it to a graphics package to show real-time behavior of your solution. Section III provides benchmarks for you to run implementation and collect data. Section IV provides general format requirements and grading details for the project report. Section V provides more details of different requirements for each part.