Maximum weight independent sets in hole- and co-chair-free graphs

DOI10.1016/J.IPL.2011.09.015zbMATH Open1233.68139OpenAlexW1989539462MaRDI QIDQ763494FDOQ763494

Authors: Andreas Brandstädt, Vassilis Giakoumakis 

Publication date: 9 March 2012

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2011.09.015

Recommendations

• Addendum to: ``Maximum weight independent sets in hole- and co-chair-free graphs
• Independent Sets in Classes Related to Chair-Free Graphs
• Maximum weight independent sets in hole- and dart-free graphs
• Maximum weight independent sets in odd-hole-free graphs without dart or without bull
• Weighted independent sets in classes of \(P_6\)-free graphs

zbMATH Keywords

graph algorithmsmodular decompositiongraph decompositionperfect graphsmaximum weight independent set problemclique separator decompositionhole-free graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Title not available (Why is that?)
• Topics in Intersection Graph Theory
• Title not available (Why is that?)
• Title not available (Why is that?)
• Graph Classes: A Survey
• Decomposition by clique separators
• Modular decomposition and transitive orientation
• The strong perfect graph theorem
• Weakly triangulated graphs
• Polynomial algorithms for the maximum stable set problem on particular classes of \(P_{5}\)-free graphs
• On the structure and stability number of \(P_{5}\)- and co-chair-free graphs
• On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
• Recognizing weakly triangulated graphs by edge separability
• Algorithms for weakly triangulated graphs
• Maximum independent sets in subclasses of \(P_{5}\)-free graphs
• On independent vertex sets in subclasses of apple-free graphs
• Finding large holes
• Improved algorithms for weakly chordal graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• A characterization of some graph classes with no long holes
• Erratum: Optimizing weakly triangulated graphs. [Graphs and Combinatorics 5, 339-349 (1989)]
• On \(\alpha\)-redundant vertices in \(P_{5}\)-free graphs

Cited In (16)

• Approximation of knapsack problems with conflict and forcing graphs
• On the maximum weight independent set problem in graphs without induced cycles of length at least five
• Graphs without large apples and the maximum weight independent set problem
• Maximum weighted independent sets on transitive graphs and applications
• Distance-\(d\) independent set problems for bipartite and chordal graphs
• Efficient robust algorithms for the maximum weight stable set problem in chair-free graph classes
• Combining decomposition approaches for the maximum weight stable set problem
• Approximation algorithm for the distance-3 independent set problem on cubic graphs
• On atomic structure of \(P_5\)-free subclasses and maximum weight independent set problem
• Maximum Weight Independent Sets in ( $$S_{1,1,3}$$ , bull)-free Graphs
• Maximum weight independent sets in hole- and dart-free graphs
• Addendum to: ``Maximum weight independent sets in hole- and co-chair-free graphs
• Maximum weight independent sets in odd-hole-free graphs without dart or without bull
• Induced subgraphs of bounded treewidth and the container method
• Approximability of the Distance Independent Set Problem on Regular Graphs and Planar Graphs
• The quadratic balanced optimization problem

This page was built for publication: Maximum weight independent sets in hole- and co-chair-free graphs

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