On a connection between facility location and perfect graphs

作     者：Baiou, Mourad Barahona, Francisco 

作者机构：CNRS LIMOS Complexe Sci Cezeaux F-63173 Aubiere France IBM Corp Thomas J Watson Res Ctr Yorktown Hts NY 10589 USA 

出 版 物：《OPERATIONS RESEARCH LETTERS》 (运筹学快报)

年 卷 期：2014年第42卷第6-7期

页      面：466-472页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070104[理学-应用数学] 0701[理学-数学] 

基　　金：project CNRS-IBM [PICS05891] 

主　　题：Uncapacitated facility location problem Perfect graphs Polyhedral combinatorics 

摘      要：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. (C) 2014 Elsevier B.V. All rights reserved.