Maximum Weight Stable Set in (P₇, bull)-free graphs and (S_1,2,3, bull)-free graphs

2016/11/29 by Maffray, Frédéric, Pastor, Lucas
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1611.09663

Abstract

We give a polynomial time algorithm that finds the maximum weight stable set in a graph that does not contain an induced path on seven vertices or a bull (the graph with vertices a, b, c, d, e and edges ab, bc, cd, be, ce). With the same arguments with also give a polynomial algorithm for any graph that does not contain S_1,2,3 or a bull.

Related

• The maximum weight stable set problem in (P₆,bull)-free graphs
• An \cal O(mlog n) algorithm for the weighted stable set problem in claw-free graphs with α(G) ≤ 3
• Maximum Weight Independent Sets for (S_1,2,4,Triangle)-Free Graphs in Polynomial Time
• Polynomial-time algorithm for Maximum Weight Independent Set on P₆-free graphs
• Maximum Weight Independent Sets for (P₇,Triangle)-Free Graphs in Polynomial Time