Martin Charles Golumbic, Renu C. Laskar
Discrete Applied Mathematics
Paper
On a connection between facility location and perfect graphs
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.
Related
John S. Lew
Mathematical Biosciences
Jonathan Ashley, Brian Marcus, et al.
Ergodic Theory and Dynamical Systems
Martin C. Gutzwiller
Physica D: Nonlinear Phenomena