Review of the Book “Optimization in Computer Engineering—Theory and Applications”: Chapter 8—Applying Graph Coloring to Frequency Assignment

doi:10.4236/wet.2012.32008

Paper Menu >>

Journal Menu >>

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.

Email: [email protected]

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/

Email: bookorder @ scirp.org