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

2015/01/23 by Paolo Nobili, Nobili, Paolo, Antonio Sassano +1
Computer Science · Engineering · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Optimization and Packing Problems

paper · pdf · doi:10.48550/arxiv.1501.05851

openalex publication_date 2015/01/23 · openalex created_date 2018/02/02 · openalex updated_date 2026/07/28

Abstract

In this paper we show that a connected claw, net-free graph G(V, E) with α(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₀, …, H_p\ with the property that H_i 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 \cal O(|V|√(|E|)).

Related

• An \cal O(n² log(n)) algorithm for the weighted stable set problem in claw-free graphs
• An \cal O(mlog n) algorithm for the weighted stable set problem in claw-free graphs with α(G) ≤ 3
• The maximum weight stable set problem in (P₆,bull)-free graphs
• Maximum Weight Stable Set in (P₇, bull)-free graphs and (S_1,2,3, bull)-free graphs
• Max Weight Independent Set in graphs with no long claws: An analog of the Gyárfás' path argument