Maximum weight independent sets in odd-hole-free graphs without dart or without bull

DOI10.1007/s00373-014-1461-xzbMath1321.05178arXiv1209.2512OpenAlexW1972095231MaRDI QIDQ497314

Andreas Brandstädt, Raffaele Mosca

Publication date: 24 September 2015

Published in: Graphs and Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

polynomial time algorithmmodular decompositionmaximum weight independent setclique separatorshole-free graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Signed and weighted graphs (05C22)

Related Items (8)

One-three join: a graph operation and its consequences ⋮ The Maximum Weight Stable Set Problem in ( $$P_6$$ , bull)-Free Graphs ⋮ 2-divisibility of some odd hole free graphs ⋮ Independent sets in some classes of \(S_{i,j,k}\)-free graphs ⋮ Subexponential-time algorithms for maximum independent set in \(P_t\)-free and broom-free graphs ⋮ A polynomial Turing-kernel for weighted independent set in bull-free graphs ⋮ Independent Sets in Classes Related to Chair-Free Graphs ⋮ Maximum Weight Independent Sets in ( $$S_{1,1,3}$$ , bull)-free Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences
• On the structure of bull-free perfect graphs
• Maximum weight independent sets in hole- and dart-free graphs
• Maximum weight independent sets in hole- and co-chair-free graphs
• The structure of bull-free graphs II and III -- a summary
• On independent vertex sets in subclasses of apple-free graphs
• The strong perfect graph theorem
• Finding large holes
• Stability number of bull- and chair-free graphs
• Modular decomposition and transitive orientation
• A decomposition for a class of \((P_ 5,\overline{P}_ 5)\)-free graphs
• Stability number of bull- and chair-free graphs revisited
• Some results on maximum stable sets in certain \(P_{5}\)-free graphs
• (\(P_{5}\), diamond)-free graphs revisited: Structure and linear time optimization.
• Algorithms for weakly triangulated graphs
• A characterization of some graph classes with no long holes
• Efficiently decomposing, recognizing and triangulating hole-free graphs without diamonds
• On the vertex packing problem
• Recognizing Berge graphs
• Improved algorithms for weakly chordal graphs
• A Polynomial Turing-Kernel for Weighted Independent Set in Bull-Free Graphs
• Recognizing Dart-Free Perfect Graphs
• Rose window graphs
• Graph Classes: A Survey
• Odd Hole Recognition in Graphs of Bounded Clique Size

This page was built for publication: Maximum weight independent sets in odd-hole-free graphs without dart or without bull