An algorithm for the weighted stable set problem in claw-free graphs with

作者：Nobili Paolo; Sassano Antonio^*

来源：Mathematical Programming, 2017, 164(1-2): 157-165.

DOI：10.1007/s10107-016-1080-9

• Claw-free graphs
• Stable set
• Algorithms

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.

• 出版日期2017-7