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

DOI10.1007/978-3-662-53536-3_8MaRDI QIDQ3181049zbMATH OpenOpenAlexFDO

Authors Frédéric Maffray, Lucas Pastor

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

\(P_6\)-free graphbull-free graphpolynomial time algorithmstability

Mathematics Subject Classification ID

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

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$).

Recommendations

• Maximum weight stable set in (\(P_7\), bull)-free graphs and (\(S_{1, 2, 3}\), bull)-free graphs
• Polynomial-time algorithm for maximum weight independent set on \(P_6\)-free graphs
• A polynomial Turing-kernel for weighted independent set in bull-free graphs
• Optimizing Bull-Free Perfect Graphs
• Coloring bull-free perfect graphs

Cites work

• 4-coloring \((P_6, \text{bull})\)-free graphs
• A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
• A polynomial Turing-kernel for weighted independent set in bull-free graphs
• Coloring bull-free perfect graphs
• Handle-rewriting hypergraph grammars
• scientific article; zbMATH DE number 3168327 (Why is no real title available?)
• scientific article; zbMATH DE number 5761816 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1420904 (Why is no real title available?)
• scientific article; zbMATH DE number 5279372 (Why is no real title available?)
• Independence and efficient domination on \(P_6\)-free graphs
• Independent sets in extensions of 2\(K_{2}\)-free graphs
• Linear time solvable optimization problems on graphs of bounded clique-width
• Maximum weight independent sets in (P₆, co-banner)-free graphs
• Maximum weight independent sets in odd-hole-free graphs without dart or without bull
• On the structure of bull-free perfect graphs
• Optimizing Bull-Free Perfect Graphs
• Polynomial algorithm for finding the largest independent sets in graphs without forks
• Recognizing bull-free perfect graphs
• Stable sets in certain \(P_6\)-free graphs
• The strong perfect graph theorem
• 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
• Weighted independent sets in a subclass of P₆-free graphs
• Weighted independent sets in classes of \(P_6\)-free graphs

Cited in

(7)

• Stability number of bull- and chair-free graphs
• Maximum weight stable set in (\(P_7\), bull)-free graphs and (\(S_{1, 2, 3}\), bull)-free graphs
• Stable sets in \(\{\mathrm{ISK4,wheel}\}\)-free graphs
• 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
• A polynomial Turing-kernel for weighted independent set in bull-free graphs
• Polynomial cases for the vertex coloring problem

This page was built for publication: The maximum weight stable set problem in (\(P_6\), bull)-free graphs

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