Models and Algorithms for Some Covering Problems on Graphs

Several real-life problems as well as problems of theoretical importancewithin the field of Operations Research are combinatorial in nature.Combinatorial Optimization deals with decision-making problems definedon a discrete space. Out of a finite or countably infinite set offeasible solutions, one has to choose the best one according to an objectivefunction. Many of these problems can be modeled on undirectedor directed graphs. Some of the most important problems studied inthis area include the Minimum Spanning Tree Problem, the TravelingSalesman Problem, the Vehicle Routing Problem, the Matching Problem,the Maximum Flow Problem. Some combinatorial optimization problemshave been modeled on colored (labeled) graphs. The colors can beassociated to the vertices as well as to the edges of the graph, dependingon the problem. The Minimum Labeling Spanning Tree Problem andthe Minimum Labeling Hamiltonian Cycle Problem are two examplesof 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 whichno polynomial time algorithm exists. Many of the well-known combinatorialoptimization problems defined on graphs are hard problems ingeneral. However, if we know more about the structure of the graph,the problems can become more tractable. In some cases, they can evenbe shown to be polynomial-time solvable. This particularly holds fortrees. .. [edited by Author]