Maximum weight stable set in (P₇, bull)-free graphs and (S₁, 2, 3, bull)-free graphs

DOI10.1016/J.DISC.2017.10.004zbMATH Open1383.05145arXiv1611.09663OpenAlexW2617352957MaRDI QIDQ1709548FDOQ1709548

Authors: Frédéric Maffray, Lucas Pastor 

Publication date: 5 April 2018

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

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.

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

Recommendations

• Stable sets of maximum weight in (\(P_{7}\), banner)-free graphs
• The maximum weight stable set problem in (\(P_6\), bull)-free graphs
• Maximum Weight Independent Sets in ( $$S_{1,1,3}$$ , bull)-free Graphs
• Some observations on maximum weight stable sets in certain \(P_{5}\)-free graphs
• Maximum weight independent sets for (\(P_7\), triangle)-free graphs in polynomial time
• Maximum weight independent sets in odd-hole-free graphs without dart or without bull
• Some results on maximum stable sets in certain \(P_{5}\)-free graphs
• Maximum stable sets in analogs of Kneser and complete graphs
• Maximum-weight stable sets and safe lower bounds for graph coloring
• On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem

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 algorithms (graph-theoretic aspects) (05C85) Graph polynomials (05C31) Signed and weighted graphs (05C22)

Cites Work

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

Cited In (6)

• Maximum Weight Independent Sets in ( $$S_{1,1,3}$$ , bull)-free Graphs
• Stability number of bull- and chair-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
• Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in \(\boldsymbol{H}\)-Free Graphs
• Maximum weight independent sets for (\(P_7\),triangle)-free graphs in polynomial time

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1709548)