Jonathan Ashley, Brian Marcus, et al.
Ergodic Theory and Dynamical Systems
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
Fausto Bernardini, Holly Rushmeier
Proceedings of SPIE - The International Society for Optical Engineering
Yixiong Chen, Weichuan Fang
Engineering Analysis with Boundary Elements
A.R. Conn, Nick Gould, et al.
Mathematics of Computation