Moutaz Fakhry, Yuri Granik, et al.
SPIE Photomask Technology + EUV Lithography 2011
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
J.P. Locquet, J. Perret, et al.
SPIE Optical Science, Engineering, and Instrumentation 1998
W.C. Tang, H. Rosen, et al.
SPIE Optics, Electro-Optics, and Laser Applications in Science and Engineering 1991
Martin Charles Golumbic, Renu C. Laskar
Discrete Applied Mathematics