Maximum weight stable set in (\(P_7\), bull)-free graphs and (\(S_{1, 2, 3}\), bull)-free graphs

DOI10.1016/j.disc.2017.10.004zbMath1383.05145arXiv1611.09663OpenAlexW2617352957MaRDI QIDQ1709548

Frédéric Maffray, Lucas Pastor

Publication date: 5 April 2018

Published in: Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

polynomial algorithmmaximum weight stable set problem(\(P_7\), bull)-free graph(\(S_{1, 2, 3}\),bull)-free graph

Mathematics Subject Classification ID

Graph polynomials (05C31) Graph algorithms (graph-theoretic aspects) (05C85) Signed and weighted graphs (05C22)

Related Items (4)

Maximum weight independent sets for (\(P_7\),triangle)-free graphs in polynomial time ⋮ Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in \(\boldsymbol{H}\)-Free Graphs ⋮ Maximum weight independent sets for (\(S_{1,2,4}\),triangle)-free graphs in polynomial time ⋮ Independent sets in \((P_4+P_4\),triangle)-free graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Weighted independent sets in classes of \(P_6\)-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
• On maximal independent sets of vertices in claw-free graphs
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• Stable sets in certain \(P_6\)-free graphs
• Efficient algorithms for minimum weighted colouring of some classes of perfect graphs
• Recognizing bull-free perfect graphs
• Maximum weight independent sets in (\(P_6\), co-banner)-free graphs
• An \(\mathcal{O}(m\log n)\) algorithm for the weighted stable set problem in claw-free graphs with \(\alpha ({G}) \leq 3\)
• Stable sets of maximum weight in (\(P_{7}\), banner)-free graphs
• Maximum Weight Independent Sets in ( $$S_{1,1,3}$$ , bull)-free Graphs
• A Polynomial Turing-Kernel for Weighted Independent Set in Bull-Free Graphs
• The Maximum Weight Stable Set Problem in ( $$P_6$$ , bull)-Free Graphs
• Four classes of perfectly orderable graphs
• A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
• Optimizing Bull-Free Perfect Graphs
• Coloring Bull-Free Perfect Graphs
• Independent Set in P₅-Free Graphs in Polynomial Time
• A polynomial algorithm to find an independent set of maximum weight in a fork-free graph

This page was built for publication: Maximum weight stable set in (\(P_7\), bull)-free graphs and (\(S_{1, 2, 3}\), bull)-free graphs