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

Maximum Clique Conformance Measure for Graph Coloring Algorithms

by Abdulmutaleb Alzubi, Mohammad Al-Haj Hassan, Mohammad Malkawi
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 127 - Number 11
Year of Publication: 2015
Authors: Abdulmutaleb Alzubi, Mohammad Al-Haj Hassan, Mohammad Malkawi
10.5120/ijca2015906540

Abdulmutaleb Alzubi, Mohammad Al-Haj Hassan, Mohammad Malkawi . Maximum Clique Conformance Measure for Graph Coloring Algorithms. International Journal of Computer Applications. 127, 11 ( October 2015), 32-37. DOI=10.5120/ijca2015906540

@article{ 10.5120/ijca2015906540,
author = { Abdulmutaleb Alzubi, Mohammad Al-Haj Hassan, Mohammad Malkawi },
title = { Maximum Clique Conformance Measure for Graph Coloring Algorithms },
journal = { International Journal of Computer Applications },
issue_date = { October 2015 },
volume = { 127 },
number = { 11 },
month = { October },
year = { 2015 },
issn = { 0975-8887 },
pages = { 32-37 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume127/number11/22774-2015906540/ },
doi = { 10.5120/ijca2015906540 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T23:18:39.974364+05:30
%A Abdulmutaleb Alzubi
%A Mohammad Al-Haj Hassan
%A Mohammad Malkawi
%T Maximum Clique Conformance Measure for Graph Coloring Algorithms
%J International Journal of Computer Applications
%@ 0975-8887
%V 127
%N 11
%P 32-37
%D 2015
%I Foundation of Computer Science (FCS), NY, USA
Abstract

The Graph Coloring Problem (GCP) is an essential problem in graph theory, and it has many applications such as the exam scheduling problem, register allocation problem, timetabling, and frequency assignment. The maximum clique problem is also another important problem in graph theory and it arises in many real life applications like managing the social networks. These two problems have received a lot of attention by the scientists, not only for their importance in the real life applications, but also for their theoretical aspect. Solving these problems however remains a challenge, and the proposed algorithms for this purpose apply to rather small graphs, whereas many real life application graphs encompass hundreds or thousands of nodes. This paper presents a new measure for evaluating the efficiency of graph coloring algorithms. The new measure computes the clique conformance index (CCI) of a graph coloring algorithm. CCI measures the rate of deviation of a coloring algorithm from the maximum clique during the process of coloring a graph. The paper presents empirical measurement for two coloring algorithms proposed by the authors.

References
  1. Allen, M., Kumaran, G., & Liu, T. (2002). A combined algorithm for graph-coloring in register allocation, Proceedings of the Computational Symposium on Graph Coloring and its Generalizations, pp. 100–111.
  2. Bacs´o, G. S., et al , Coloring the maximal cliques of graphs. SIAM J. Discrete Math., Vol. 17, No. 3, pp. 361–376, 2004.
  3. Balas, E., & Yu, C. S. (1986). Finding a maximum clique in an arbitrary graph. SIAM J. Comput , Vol 15, No. 4, pp 1054-1068.
  4. Balasundaram, B ., and Butenko, S., (2011), Clique relaxations in social network analysis: The maximum k-plex problem, Operations Research, Vol. 59, Issue 1, pp. 133–142.
  5. Caramia, M., & Dell’Olmo, P. (2001). Iterative Coloring Extension of a Maximum Clique. Naval Research Logistics (NRL), Vol. 48, Issue 6, pp. 518–550.
  6. D´efossez, D., (2006), Clique-coloring some classes of odd-hole-free graphs. Journal of Graph Theory, Vol. 53, Issue 3, pp. 233–249.
  7. Duffus, D., et al, (1991), Two-colouring all two-element maximal anti-chains. J. Combinatorial Theory Ser. A, Vol. 57, Issue 1, pp. 109–116.
  8. Gravier, S., Ho`ang, C. T., and Maffray, F., (2003), Coloring the hypergraph of maximal cliques of a graph with no long path, Discrete Math., Vol. 272, No. (2-3), pp. 285–290.
  9. Hosseini, S.H. , et al., (1990). Analysis of a Graph Coloring Based Distributed Load Balancing Algorithm. Journal of Parallel & Distributed Systems , Vol. 10. , Issue 2, pp. 160–166
  10. Jensen, T. R., & Toft, B. (1994). Graph Coloring Problems, John Wiley & Sons, USA.
  11. Magnus, M. H. (1991). Frugal methods for the independent set and graph coloring problems. PhD thesis, The State University of New Jersey, New Brunswick, New Jersey.
  12. Malkawi, M., Hajhassan, M., & Hajhasan, O. (2008). New exam scheduling algorithm using graph coloring. International Arab Journal for IT (IAJIT)Vol. 5, No. 1, pp 80-86.
  13. Robson, J. M. (1986). Algorithms for maximum independent set . J. Algorithms , Vol. 7, pp 425-440.
  14. Tomita, A., Tanaka, A., & Takahashi, H. (2006). The worst-case time complexity for generating all maximal cliques and computational experiments, Theoretical Computer Science 363 (2006), pp 28 – 42.
  15. Xiao, M., (2010), A Simple and Fast Algorithm for Maximum Independent Set in 3-Degree Graphs, Proceedings of the 4th International Workshop, WALCOM: Algorithms and Computations, pp. 281-292.
Index Terms

Computer Science
Information Sciences

Keywords

Algorithms Clique conformance Index Convergence Rate Deviation Rate Graph Coloring Maximum Clique.

Powered by PhDFocusTM