Title :
Performance Profile of a Hybrid Heuristic Search Technique Using Graph Coloring as a Seed Example
Author :
Pal, Anindya J. ; Sarma, Samar S. ; Ray, Biman
Author_Institution :
Heritage Inst. of Technol., Kolkata
Abstract :
Design and analysis of new algorithms are ever going phenomena in life of computer scientists. NP problems are attracting designers to design both heuristic and approximate algorithms that can result in better optimal and time-space efficient algorithms. Here, we have designed a memetic algorithm (also known as metaheuristic or hybrid heuristic), for optimal vertex coloring of a simple, symmetric and connected graph. Other than various uses, the problem has a perfume of efficient algorithm design in large-scale test graph. The earlier works, though encouraging, could not draw a conclusion that is deterministic. This paper is an essay towards further information in this area. Our work is progressing, but we don´t know whether better players are needed for final bet through in this particular algorithm design
Keywords :
approximation theory; computational complexity; graph colouring; search problems; NP problems; approximate algorithm; graph coloring; hybrid heuristic algorithm; hybrid heuristic searching; memetic algorithm; metaheuristic algorithm; vertex coloring; Algorithm design and analysis; Circuit testing; Educational institutions; Heuristic algorithms; Job shop scheduling; Large-scale systems; Performance analysis; Processor scheduling; Registers; Simulated annealing; GA; NP; memetic algorithm; metaheuristic; vertex coloring;
Conference_Titel :
Cognitive Informatics, 2006. ICCI 2006. 5th IEEE International Conference on
Conference_Location :
Beijing
Print_ISBN :
1-4244-0475-4
DOI :
10.1109/COGINF.2006.365560