Wireless Engineering and Technology, 2012, 3, 51-51
http://dx.doi.org/10.4236/wet.2012.32008 Published Online April 2012 (http://www.SciRP.org/journal/wet)
Review of the Book “Optimization in Computer
Engineering—Theory and Applications”: Chapter
8—Applying Graph Coloring to Frequency Assignment
Andras Orban
Staff Software Engineer, Google Switzerland, Swizerland.
Received April 11th, 2012
ISBN: 978-1-935068-58-7
190pp Pub.date: November 2011
Price: $89
This book focuses on the relationship between theory and
applications of various optimization problems in com-
puter engineering. In the first half of the book the theo-
retical foundations are presented, such as some selected
graph algorithms, integer linear programming and com-
plexity theory. The second half of the book brings the
theory closer to the reader by applying them to
real-world optimization problems. Its aim is to bridge the
often significant gap between theory and applications
bringing additional value to both: the theory becomes
more interesting in light of a possible application and
understanding the hardness and possible solutions of the
real-world problem definitely benefits from a strong
theoretical background.
Chapter 8 is a good example of the above. Here the
authors present several versions of the frequency as-
signment problem (FAP), which is an important practical
optimization problem arising in wireless network design.
It is shown how FAP can be reduced to the earlier pre-
sented graph coloring problem. It is interesting to note
that often the practical problem needs significant simpli-
fication in order to fit into the model that the theory is
able to handle, or the theoretical problem needs to be
extended to be able to model the needs of the practical
application. Various generalizations of the simple graph
coloring problem such as list coloring and T-coloring are
introduced to model the constraints of the FAP. With this
reduction the specific engineering problem can be han-
dled throug h well-unders t o od mathem atical model s.
Besides showing the reduction to the graph coloring
problem, the authors apply a graph coloring solver on
industry benchmark FAP instances to further understand
the characteristics of the real-world FAP. They show that
there are significant differences in the difficulty of the
problem on random and real-world graphs and that the
parameters of the particular instance play a crucial role in
the hardness of the problem. They show that the FAPs
show a phase transition property in every input parameter,
ie. there is a critical parameter combination where the
problem gets extremely hard, but otherwise the problem
can be solved relatively easily even on large real-world
networks.
Readers will surely benefit from the unique nature of
the book that brings theory and applications close to-
gether in a well-understandable yet theoretical ly solid way .
To order:
http://www.scirp.org/book/
C
opyright © 2012 SciRes. WET