Home » Publication » 16461

Dettaglio pubblicazione

2017, MATHEMATICAL PROGRAMMING, Pages 157-165 (volume: 164)

An O(mlogn) algorithm for the weighted stable set problem in claw-free graphs with α(G)≤3 (01a Articolo in rivista)

Nobili Paolo, Sassano Antonio

In this paper we show how to solve the Maximum Weight Stable Set Problem in a claw-free graph G(V, E) with α(G)≤3α(G)≤3 in time O(|E|log⁡|V|). More precisely, in time O(|E|) we check whether α(G)≤3or produce a stable set with cardinality at least 4; moreover, if α(G)≤3 we produce in time O(|E|log|V|) a maximum weight stable set of G. This improves the bound of O(|E||V|) due to Faenza, Oriolo and Stauffer.
Gruppo di ricerca: Combinatorial Optimization
keywords
© Università degli Studi di Roma "La Sapienza" - Piazzale Aldo Moro 5, 00185 Roma