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

DOI10.1016/J.IPL.2011.09.015MaRDI QIDQ763494zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3906240 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1445284 (Why is no real title available?)
• scientific article; zbMATH DE number 3893228 (Why is no real title available?)
• A characterization of some graph classes with no long holes
• Algorithms for weakly triangulated graphs
• Decomposition by clique separators
• Erratum: Optimizing weakly triangulated graphs. [Graphs and Combinatorics 5, 339-349 (1989)]
• Finding large holes
• Graph Classes: A Survey
• Improved algorithms for weakly chordal graphs
• Maximum independent sets in subclasses of \(P_{5}\)-free graphs
• Modular decomposition and transitive orientation
• On \(\alpha\)-redundant vertices in \(P_{5}\)-free graphs
• On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
• On independent vertex sets in subclasses of apple-free graphs
• On the structure and stability number of \(P_{5}\)- and co-chair-free graphs
• Polynomial algorithms for the maximum stable set problem on particular classes of \(P_{5}\)-free graphs
• Recognizing weakly triangulated graphs by edge separability
• The strong perfect graph theorem
• Topics in Intersection Graph Theory
• Weakly triangulated 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
• Approximation algorithm for the distance-3 independent set problem on cubic graphs
• Combining decomposition approaches for the maximum weight stable set problem
• On atomic structure of \(P_5\)-free subclasses and maximum weight independent set problem
• Maximum weight independent sets in hole- and dart-free graphs
• Maximum Weight Independent Sets in ( $$S_{1,1,3}$$ , bull)-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
• Approximability of the Distance Independent Set Problem on Regular Graphs and Planar Graphs
• Induced subgraphs of bounded treewidth and the container method
• 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)