Publication
Operations Research Letters
Paper

On a connection between facility location and perfect graphs

View publication

Abstract

We characterize the graphs for which a linear relaxation of a facility location problem defines a polytope with all integral extreme points. We use a transformation to a stable set problem in perfect graphs. Based on this transformation, these graphs can be recognized in polynomial time.

Date

Publication

Operations Research Letters

Authors

Topics

Share