The Maximum Weight Stable Set Problem in ( $$P_6$$ , bull)-Free Graphs
From MaRDI portal
Publication:3181049
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
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 P6-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