DII CGO
inicioir al DIIbuscar
fcfm
top
topleft
on a connection between facility location and perfect graphs

Given a directed graph where each arc and node is associated with a weight, the {\it uncapacitated facility location problem} (UFLP) is the problem that select some nodes and assigning the non selected ones to these nodes, such that the overall weight is minimized. In the case where some non selected nodes may or not be assigned to a selected one, the problem is known as the {\it prize collecting uncapacitated facility location problem} (PCUFLP). In a previous work, we have characterized all the graphs such that the associated classical linear relaxation of PCUFLP has all its extreme points in 0-1. This has been done by mainly applying a so-called labeling procedure. The natural question that has been asked is about the characterization of graphs for which the linear relaxation of UFLP is integral. In this talk we will show that is impossible to extend this labeling procedure to have such a   characterization. Instead, we give a characterization by using the complete description of the stable set polytope in perfect graphs.