Journal of Software Engineering and Applications, 2012, 5, 109-109 Published Online March 2012 (
Optimization in Computer Engineering—Theory and
Applications: Book Review of Chapter 8—Applying Graph
Coloring to Frequency Assignment
Ridha Khedri
McMaster University, Ha milton, Cana da.
Received March 22, 2012
ISBN: 978-1-935068-58-7
190pp November 2011
Price: $89
The chapter gives a concise and clear presentation of the
basic concepts and the variants of the graph coloring
problem. It discusses the link between these variants. It
uses a very simple and clear language that is at the grasp
of an average engineering or science undergraduate stu-
dent. It then focuses on discussing the app licability of the
graph coloring problem to Frequency Assignment Prob-
lem (FAP). It precisely selects a special case of this
problem: the Fixed Channel Assignment (FCA).
The chapter gives a clear explanation of the common
application domains of the Frequency Assignment prob-
lem such as radio and television transmission, military
applications needs, satellite communication, and fre-
quency planning of WLANs. The transition from FAP to
graph coloring problem is well explained by using simple
examples and graphical illustrations. The empirical as-
sessment of the efficiency of the applied algorithm on
FAP instance and random graphs is presented by giving
the process, and the results. The implementation is car-
ried using the Budapest Complexity Analysis Toolkit
The content of the chapter is expected to age grace-
fully. It tackles a problem that is relevant today and will
remain pertinent for many years to come. The title of the
chapter is accurate. It captures the method and the sub-
ject that is tackled in the chapter. The examples are sim-
ple and easy to follow and the illustrations are appropri-
ate and well executed.
The chapter is not only written is a clear natural lan-
guage but also complying with technical accuracy, which
makes its content accessible and suitable to a variety of
readers. A reader with a basic background in optimiza-
tion has access to the material presented in the chapter.
At the same time, an expert can find very interesting the
empirical assessment of the complexity of solving FAPs.
The chapter would benefit from a better explanation
for the rational of the empirical study. Explaining the
reasons for focussing the study on increasing edge den-
sity, increasing the number of vertices, and on increasing
the number of colors would help a non-expert reader un-
derstand its rational.
In general the chapter is a wellarticulate piece of work
and presents a lasting contribution to the field that is ac-
cessible to a wide audience.
To order:
opyright © 2012 SciRes. JSEA