Optimization problems can be naturally divided into two categories: continuous
and discrete. Continuous optimization problems are those that allow continuous
variables. Generally speaking the aim of such problems is to find a set of real
numbers or a real function, which optimize a certain criterion. On the other hand,
discrete optimization problems are those that contain discrete variables. The aim of
such problems is to find a combinatorial object, which optimizes a certain criterion
function in a finite space of legal solutions. On the whole, each of these two types
of problems requires separate solution techniques. This book is devoted to selected
problems of combinatorial optimization, otherwise known as discrete optimization.
The fact that such combinatorial calculations are becoming increasingly important
stimulates research and development of the field. Common programmers' expe-
rience shows that the number of combinatorial computations appearing in user
programs increases more rapidly than the number of numerical computations. The
reason for this is that besides the traditional fields of applications of mathematics
in engineering and physics, discrete structures appear now more frequently than
continuous ones. Discrete optimization is a branch of applied mathematics and
theoretical computer science that includes various topics of graph theory, network
design, mathematical programming, sequencing and scheduling, as well as many
others. One of its areas is graph coloring, to which this book is entirely devoted.
Graph coloring
Graph coloring is one of the oldest and best-known problems of graph theory.
As people became accustomed to applying the tools of graph theory to the solu-
tion of real-world technological and organizational problems, new chromatic models
emerged as a natural way of tackling many practical situations. Internet statistics
show that graph coloring is one of the central issues in the collection of several
hundred classical combinatorial problems
The reason for this is the simplicity
of its formulation and seemingly natural solution on the one hand, and numerous
potential applications on the other. Unfortunately, high computational complexity
prevents the efficient solution of numerous problems by means of graph coloring.
For example, the deceptively simple task of deciding if the chromatic number of
a graph, i.e. the smallest number of colors that can be assigned to the vertices of
a graph so that no pair of adjacent vertices is colored with the same color, is at
most 3 remains NP-complete
In practice this means that our task cannot be
solved in polynomial time and, consequently, it is impossible to find a chromatic
solution to a graph on several dozens of vertices in a reasonable time. Needless
to say, graphs of this size are definitely too small to be considered satisfactory in
practical applications.
Previous Page Next Page