Discover Your Island University

Graduate Projects

View

Project ID: 280
Author: Praveen Nuthulapati
Project Title: Decision Fusion of Combinatorial Optimization Algorithms for Solving the Graph Coloring Problem
Semester: Fall 2006
Committe Chair: Dr. Ajay Katangur
Committee Member 1: Dr. David Thomas
Committee Member 2: Dr. Long-Zhuang Li
Project Description: The graph coloring problem is a practical method of representing many real world problems including time scheduling, frequency assignment, register allocation, and circuit board testing. The most important fact that makes graph coloring exciting is that finding the minimum number of colors for an arbitary graph is NP-hard. This project implements genetic algorithm, the the simulated annealing algorithm, the highest order algorithm and the sequential algorithm to find a solution for the graph coloring problem. Decision Fusion is then applied on the implemented algorighms to find an optimized solution. Applying decision fusion on the algorithms signifies the importance given to the factors such as the time of execution of availability of processing resources. Extensive testing and evaluations has been performed to determine important parameters and the efficiency of the simulator.
Project URL:   280.pdf