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

DOI10.1016/j.ipl.2011.09.015zbMath1233.68139OpenAlexW1989539462MaRDI QIDQ763494

Vassilis Giakoumakis, Andreas Brandstädt

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

zbMATH Keywords

graph algorithmsperfect graphsmodular decompositiongraph decompositionmaximum weight independent set problemclique separator decompositionhole-free graphs

Mathematics Subject Classification ID

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

Related Items (10)

On atomic structure of \(P_5\)-free subclasses and maximum weight independent set problem ⋮ Combining decomposition approaches for the maximum weight stable set problem ⋮ Approximability of the Distance Independent Set Problem on Regular Graphs and Planar Graphs ⋮ Distance-\(d\) independent set problems for bipartite and chordal graphs ⋮ Approximation Algorithm for the Distance-3 Independent Set Problem on Cubic 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 ⋮ Approximation of knapsack problems with conflict and forcing graphs ⋮ Maximum weight independent sets in hole- and dart-free graphs ⋮ The quadratic balanced optimization problem

Cites Work

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

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