Please use this identifier to cite or link to this item: http://elea.unisa.it:8080/xmlui/handle/10556/2303
Title: Models and Algorithms for Some Covering Problems on Graphs
Authors: Silvestri, Selene
Costagliola, Gennaro
Cerulli, Raffaele
Laporte, Gilbert
Keywords: Spanning tree
Cycle cover
Branch and cut
Issue Date: 12-May-2016
Publisher: Universita degli studi di Salerno
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]
Description: 2014 - 2015
URI: http://hdl.handle.net/10556/2303
http://dx.doi.org/10.14273/unisa-719
Appears in Collections:Informatica

Files in This Item:
File Description SizeFormat 
tesi S. Silvestri.pdftesi di dottorato2,88 MBAdobe PDFView/Open
abstract in italiano S.Silvestri.pdfabstract in italiano a cura dell'autore51,66 kBAdobe PDFView/Open
abstract in inglese S.Silvestri.pdfabstract in inglese a cura dell'autore47,72 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.