The maximum weight stable set problem in (P₆,bull)-free graphs

2016/02/22 by Frédéric Maffray, Maffray, Frédéric, Lucas Pastor +1
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Search Problems

paper · pdf · doi:10.48550/arxiv.1602.06817

openalex publication_date 2016/02/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We present a polynomial-time algorithm that finds a maximum weight stable set in a graph that does not contain as an induced subgraph an induced path on six vertices or a bull (the graph with vertices a, b, c, d, e and edges ab, bc, cd, be, ce).

Related

• Maximum Weight Stable Set in (P₇, bull)-free graphs and (S_1,2,3, bull)-free graphs
• An \cal O(mlog n) algorithm for the weighted stable set problem in claw-free graphs with α(G) ≤ 3
• Polynomial-time algorithm for Maximum Weight Independent Set on P₆-free graphs
• An \cal O(n² log(n)) algorithm for the weighted stable set problem in claw-free graphs
• An \cal O(n√(m)) algorithm for the weighted stable set problem in claw, net-free graphs with α(G) ≥ 4