Research Article
A Novel Exact Heuristic Graph Coloring Algorithm based on Finding Independent Set
|
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
|
| Volume 179 - Issue 8 |
| Published: Dec 2017 |
| Authors: Sukrati Agrawal, Vishal Chhabra |
10.5120/ijca2017916013
|
Sukrati Agrawal, Vishal Chhabra . A Novel Exact Heuristic Graph Coloring Algorithm based on Finding Independent Set. International Journal of Computer Applications. 179, 8 (Dec 2017), 15-18. DOI=10.5120/ijca2017916013
@article{ 10.5120/ijca2017916013,
author = { Sukrati Agrawal,Vishal Chhabra },
title = { A Novel Exact Heuristic Graph Coloring Algorithm based on Finding Independent Set },
journal = { International Journal of Computer Applications },
year = { 2017 },
volume = { 179 },
number = { 8 },
pages = { 15-18 },
doi = { 10.5120/ijca2017916013 },
publisher = { Foundation of Computer Science (FCS), NY, USA }
}
%0 Journal Article
%D 2017
%A Sukrati Agrawal
%A Vishal Chhabra
%T A Novel Exact Heuristic Graph Coloring Algorithm based on Finding Independent Set%T
%J International Journal of Computer Applications
%V 179
%N 8
%P 15-18
%R 10.5120/ijca2017916013
%I Foundation of Computer Science (FCS), NY, USA
Abstract
Vertex coloring is a graph coloring technique which has a wide application area to provide solution for many real world problems. The high computational complexity of graph coloring algorithm led the development of exact heuristic algorithm which can be executed in optimal time. This paper explores some existing graph coloring algorithms to propose taxonomy of exact graph coloring algorithm which is capable to execute large graphs also. This paper presented experimental result on DIMACS graph instances.
References
- Hussin B., Basari A. S. H., Shibghatullah A. S. and Asmai S. A., Exam Timetabling Using Graph Colouring Approach, In Proc. IEEE Conference on Open Systems, Langkawi, 25-28 September (2011), p.139-144.
- Chaitin G. J., Register Allocation & Spilling via Graph Coloring, In Proc. SIGPLAN '82 Proceedings of the 1982 SIGPLAN symposium on Compiler construction, June (1982), p.98-105.
- S. Ahmed, "Applications of Graph Coloring in Modern Computer Science", International Journal of Computer and Information Technology, 2012, Vol. 3, Issue 2, pp. 1-7.
- Barnier N. and Brisset P., “Graph Coloring for Air Traffic Flow Management”, Annals of Operations Research, 130 (1-4), 163–178, August (2004).
- A. Gupta and H. Patidar, “A Survey on Heuristic Graph Coloring Algorithm”, International Journal for Scientific Research & Development Vol. 4, Issue 04, 2016, pp. 297-301.
- Mahmoudia S., Lotfi S., "Modified Cuckoo Optimization Algorithm (MCOA) to Solve Graph Coloring Problem", Applied Soft Computing, 33, 48-64 (2015).
- Torkestani J. A., Meybodi M.R., “A cellular learning automata-based algorithm for solving the vertex coloring problem”, Expert Systems with Applications, 38, 9237–9247, (2011).
- Patidar H., Chakrabarti P., “ Sequential and Parallel Approaches in Context to Graph Coloring Problems - A Survey”, International Journal of Computer Systems, Volume 03– Issue 05, May, 201, pp. 403-406.
- Allwright JR, Bordawekar R, Codington PD, Dincer K, Martin CL,“A comparison of parallel graph coloring algorithms Technical” Report SCCS-666, Northeast Parallel Architecture Center, Syracuse University, 1995.
- Dr. Hussein Al-Omari and KhairEddinSabri: “New Graph Coloring Algorithms”, American Journal of Mathematics and Statistics 2 (4): 739-741, 2006ISSN 1549-3636, March 2006.
- C. Avanthay, A. Hertz, N. Zufferey, “A variable neighborhood search for graph coloring”, European Journal of Operational Research 151 (2) (2003) 379–388.
- E.K. Burke, B. McCollum, A. Meisels, S. Petrovic, R. Qu, “A graph-based hyper heuristic for timetabling problems”, European Journal of Operational Research 176 (2007) 177–192.
- E. Falkenauer, “A hybrid grouping genetic algorithm for been packing”, Journal of Heuristics 2 (1) (1996) 5–30.
- D. W. Matula and L. L. Beck. “Smallest-last ordering and clustering and graph coloring algorithms”, JACM, 1983.
- DIMACS Graph Instances, available at “http://mat.gsia.cmu.edu/COLOR/instances.html”
Index Terms
Keywords