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

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 | ) .