The Maximum Weight Stable Set Problem in ( $$P_6$$ , bull)-Free Graphs

DOI10.1007/978-3-662-53536-3_8zbMath1417.05223arXiv1602.06817OpenAlexW2283371316MaRDI QIDQ3181049

Lucas Pastor, Frédéric Maffray

Publication date: 22 December 2016

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1602.06817

zbMATH Keywords

stabilitypolynomial time algorithm\(P_6\)-free graphbull-free graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Maximum weight stable set in (\(P_7\), bull)-free graphs and (\(S_{1, 2, 3}\), bull)-free graphs ⋮ Polynomial cases for the vertex coloring problem ⋮ Maximum weight independent sets for (\(S_{1,2,4}\),triangle)-free graphs in polynomial time ⋮ Maximum Weight Independent Sets in ( $$S_{1,1,3}$$ , bull)-free Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Weighted independent sets in classes of \(P_6\)-free graphs
• Maximum weight independent sets in odd-hole-free graphs without dart or without bull
• A polynomial Turing-kernel for weighted independent set in bull-free graphs
• On the structure of bull-free perfect graphs
• The structure of bull-free graphs I -- three-edge-paths with centers and anticenters
• The structure of bull-free graphs II and III -- a summary
• The strong perfect graph theorem
• Weighted independent sets in a subclass of \(P_6\)-free graphs
• Stable sets in certain \(P_6\)-free graphs
• Independent sets in extensions of 2\(K_{2}\)-free graphs
• Recognizing bull-free perfect graphs
• Maximum weight independent sets in (\(P_6\), co-banner)-free graphs
• Linear time solvable optimization problems on graphs of bounded clique-width
• Handle-rewriting hypergraph grammars
• 4-coloring \((P_6, \text{bull})\)-free graphs
• Independence and Efficient Domination on P₆-free Graphs
• Optimizing Bull-Free Perfect Graphs
• Coloring Bull-Free Perfect Graphs
• Polynomial algorithm for finding the largest independent sets in graphs without forks
• A polynomial algorithm to find an independent set of maximum weight in a fork-free graph