| dc.description.abstract | Several real-life problems as well as problems of theoretical importance
within the field of Operations Research are combinatorial in nature.
Combinatorial Optimization deals with decision-making problems defined
on a discrete space. Out of a finite or countably infinite set of
feasible solutions, one has to choose the best one according to an objective
function. Many of these problems can be modeled on undirected
or directed graphs. Some of the most important problems studied in
this area include the Minimum Spanning Tree Problem, the Traveling
Salesman Problem, the Vehicle Routing Problem, the Matching Problem,
the Maximum Flow Problem. Some combinatorial optimization problems
have been modeled on colored (labeled) graphs. The colors can be
associated to the vertices as well as to the edges of the graph, depending
on the problem. The Minimum Labeling Spanning Tree Problem and
the Minimum Labeling Hamiltonian Cycle Problem are two examples
of problems defined on edge-colored graphs.
Combinatorial optimization problems can be divided into two groups,
according to their complexity. The problems that are easy to solve, i.e.
problems polynomially solvable, and those that are hard, i.e. for which
no polynomial time algorithm exists. Many of the well-known combinatorial
optimization problems defined on graphs are hard problems in
general. However, if we know more about the structure of the graph,
the problems can become more tractable. In some cases, they can even
be shown to be polynomial-time solvable. This particularly holds for
trees...[edited by Author] | it_IT |
