This paper aims to evaluate the research article written by Istvan Juhos and Jano van Hemert who propose a new solution to graph coloring problem. In particular, they propose the so-called Integer Merge Model (IMM) which can simplify graph coloring algorithms. It is necessary to assess this study in terms of contribution, methodology, and writing style.
Overall, one can argue that this study presents a significant contribution at to this solution of this problem. At the time when this paper was published the most common solutions to graph coloring problem (GCP) were greedy algorithms, contractions, polymonial time etc (Golumbic & Hartman, p 165). Unlike integer merge model, these methods do not heavily rely on heuristic approach which can significantly reduce the number of constraint and adjacency checks. According to the authors, traditional models require V2 while IMM needs V- k number of checks (Juhos & Hemert, 2005, p 26). The authors have discussed this model in connection DSATUR algorithm, but this method can be incorporated into other algorithms. This study can provide an incentive to further research. From this perspective, one can assign rating 5 to this study on the scale of 1 to 5.
Yet, the key limitation of this study is that Integer Merge Model was tested only on three types of algorithms, and this sampling is not quite sufficient. Certainly, this limitation does not invalidate their findings, but it makes them narrower. Moreover, they do not tell very much about the types of graphs on which the new model were tested. This is another shortcoming that one should not overlook. The authors accept the point that there are some graphs which are either too easy or too difficult for DSATUR to solve and the use of IMM does not make much difference (Juhos & Hemert, 2005, 31). It might have been necessary to test IMM on a large number of graphs and probably it was not done. So, if we are speaking about the rigor of research methodology and sampling, we can assign rating 4 to this study.
Nevertheless, one should not assume that these limitations completely diminish the significance of this study. The use of heuristic models for graph coloring still remains an open question for mathematicians and computer scientists, and this research throws a new light on this problem. Additionally, these findings can be used in different applications, such as scheduling or register allocation (Hansen & Marcotte, p 135; Appel & Ginsburg, p 260). Thus, this research serves both theoretical and practical purposes. From this point of view, this study deserves rating 4, 5.
It should be noted that this study has not been written by native speakers of English. However, this fact does not prevent the authors from expressing their thoughts and ideas quite clearly. Certainly, there are some misprints like “iff” and omissions of prepositions in some cases, but they do not distort the meaning of the sentence. Additionally, one can argue that occasionally the authors misuse punctuation marks. Still, their writing style is generally fluent and one can give these scholars 4.5 grade for their use of English. Overall, the findings presented in this research article can be of great use of computer scientists who are working on graph coloring problem because in theory, Integer Merge Model can make already-existing applications more efficient.
Works Cited
Appel Andrew and Ginsburg Maia. Modern compiler implementation in C. Cambridge: Cambridge University Press, 2004. Print.
Golumbic. Martin, and Hartman. Irith. Graph theory, combinatorics, and algorithms: interdisciplinary applications. Munich Birkhäuser, 2005. Print.
Juhos Istwan and Hemert Jano. “Increasing the efficiency of graph colouring algorithms with a representation based on vector operations”. Journal of Software 2006 1 (2), p 24- 33.
Hansen Pierre and Marcotte Odile. Graph colouring and applications. London: AMS Bookstore, 1999. Print.