An O(nm) algorithm for the weighted stable set problem in {claw, net}-free graphs with α(G)≥4α(G)≥4

In this paper we show that a connected {claw, net}-free graph G(V,E)G(V,E) with α(G)≥4α(G)≥4 is the union of a strongly bisimplicial   clique QQ 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}{H0,…,Hp} with the property that HiHi is adjacent only to Hi−1Hi−1 and Hi+1Hi+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||E|), improving the previous complexity bound of O(|V||E|)O(|V||E|).