We apologize for a recent technical issue with our email system, which temporarily affected account activations. Accounts have now been activated. Authors may proceed with paper submissions. PhDFocusTM
CFP last date
20 December 2024
Call for Paper
January Edition
IJCA solicits high quality original research papers for the upcoming January edition of the journal. The last date of research paper submission is 20 December 2024

Submit your paper
Know more
The week's pick
Responsive image
Improved Shuffled Frog Leaping Algorithm with Self-Adaptive Shuffling for Fuzzy Logic PD+G Controller Optimization in Robotic Manipulators

Duc Hoang Nguyen
Random Articles
Reseach Article

A Novel Exact Heuristic Graph Coloring Algorithm based on Finding Independent Set

by Sukrati Agrawal, Vishal Chhabra
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 179 - Number 8
Year of Publication: 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 },
issue_date = { Dec 2017 },
volume = { 179 },
number = { 8 },
month = { Dec },
year = { 2017 },
issn = { 0975-8887 },
pages = { 15-18 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume179/number8/28756-2017916013/ },
doi = { 10.5120/ijca2017916013 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-07T00:54:48.191218+05:30
%A Sukrati Agrawal
%A Vishal Chhabra
%T A Novel Exact Heuristic Graph Coloring Algorithm based on Finding Independent Set
%J International Journal of Computer Applications
%@ 0975-8887
%V 179
%N 8
%P 15-18
%D 2017
%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
  1. 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.
  2. 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.
  3. 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.
  4. Barnier N. and Brisset P., “Graph Coloring for Air Traffic Flow Management”, Annals of Operations Research, 130 (1-4), 163–178, August (2004).
  5. 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.
  6. Mahmoudia S., Lotfi S., "Modified Cuckoo Optimization Algorithm (MCOA) to Solve Graph Coloring Problem", Applied Soft Computing, 33, 48-64 (2015).
  7. 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).
  8. 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.
  9. 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.
  10. 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.
  11. C. Avanthay, A. Hertz, N. Zufferey, “A variable neighborhood search for graph coloring”, European Journal of Operational Research 151 (2) (2003) 379–388.
  12. 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.
  13. E. Falkenauer, “A hybrid grouping genetic algorithm for been packing”, Journal of Heuristics 2 (1) (1996) 5–30.
  14. D. W. Matula and L. L. Beck. “Smallest-last ordering and clustering and graph coloring algorithms”, JACM, 1983.
  15. DIMACS Graph Instances, available at “http://mat.gsia.cmu.edu/COLOR/instances.html”
Index Terms

Computer Science
Information Sciences

Keywords

Graph Coloring independent set exact algorithm approximate algorithm sequential algorithm and parallel algorithms.

Powered by PhDFocusTM