Home » Publication » 19241

Dettaglio pubblicazione

2016, DISCRETE OPTIMIZATION, Pages 63-78 (volume: 19)

An O(n√m) algorithm for the weighted stable set problem in claw, net-free graphs with α(G)≥4 (01a Articolo in rivista)

Nobili Paolo, Sassano Antonio

In this paper we show that a connected {claw, net}-free graph G ( V , E ) with α ( G ) > 3 is the union of a strongly bisimplicial clique Q and at most two clique-strips. A clique is strongly bisimplicial if its neighborhood is partitioned into two cliques which are mutually non-adjacent and a clique-strip is a sequence of cliques { H0 , ... , Hp } with the property that Hi is adjacent only to H i - 1 and H i + 1 . By exploiting such a structure we show how to solve the Maximum Weight Stable Set Problem in such a graph in time O ( | V | sqrt(| E |) ) , improving the previous complexity bound of O ( | V | | E | ) .
Gruppo di ricerca: Combinatorial Optimization
keywords
© Università degli Studi di Roma "La Sapienza" - Piazzale Aldo Moro 5, 00185 Roma