An O(n root m) algorithm for the weighted stable set problem in {claw, net}-free graphs with alpha(G) >= 4

作者：Nobili Paolo; Sassano Antonio^*

来源：Discrete Optimization, 2016, 19: 63-78.

DOI：10.1016/j.disopt.2016.01.002

• Claw-free graphs
• Net-free graphs
• Stable set
• Matching

In this paper we show that a connected {claw, net}-free graph G(V, E) with alpha(G) >= 4 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 {H-0, ... , H-p} with the property that H-i is adjacent only to Hi-1 and Hi+1. By exploiting such a structure we show how to solve the Maximum Weight Stable Set Problem in such a graph in time O(vertical bar V vertical bar root vertical bar E vertical bar) improving the previous complexity bound of O(vertical bar V vertical bar vertical bar E vertical bar).

• 出版日期2016-2