An algorithm for the weighted stable set problem in claw-free graphs with
成果类型：
Article
署名作者：
Nobili, Paolo; Sassano, Antonio
署名单位：
University of Salento; Sapienza University Rome
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-016-1080-9
发表日期：
2017
页码：
157-165
关键词：
摘要：
In this paper we show how to solve the Maximum Weight Stable Set Problem in a claw-free graph G(V, E) with in time . More precisely, in time we check whether or produce a stable set with cardinality at least 4; moreover, if we produce in time a maximum weight stable set of G. This improves the bound of due to Faenza, Oriolo and Stauffer.