Addendum to: ``Maximum weight independent sets in hole- and co-chair-free graphs

DOI10.1016/j.ipl.2014.09.019zbMath1302.68122OpenAlexW2078220006MaRDI QIDQ477686

Andreas Brandstädt, Vassilis Giakoumakis

Publication date: 9 December 2014

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

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

zbMATH Keywords

graph algorithmsperfect graphsmodular decompositionmaximum weight independent set problemclique separator decompositionodd-hole-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 (9)

One-three join: a graph operation and its consequences ⋮ Independent sets in some classes of \(S_{i,j,k}\)-free graphs ⋮ Combining decomposition approaches for the maximum weight stable set problem ⋮ Weighted independent sets in a subclass of \(P_6\)-free graphs ⋮ Weighted efficient domination in two subclasses of \(P_6\)-free graphs ⋮ Approximation of knapsack problems with conflict and forcing graphs ⋮ Independent Sets in Classes Related to Chair-Free Graphs ⋮ On the maximum independent set problem in graphs of bounded maximum degree ⋮ The maximum independent set problem in subclasses of subcubic graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On atomic structure of \(P_5\)-free subclasses and maximum weight independent set problem
• Corrigendum to our paper The ellipsoid method and its consequences in combinatorial optimization
• Maximum weight independent sets in hole- and co-chair-free graphs
• On independent vertex sets in subclasses of apple-free graphs
• The strong perfect graph theorem
• New applications of clique separator decomposition for the maximum weight stable set problem
• Decomposition by clique separators
• Modular decomposition and transitive orientation
• Efficient graph representations
• Algorithms for weakly triangulated graphs
• On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
• Recognizing Berge graphs
• Improved algorithms for weakly chordal graphs
• Independent Set in P₅-Free Graphs in Polynomial Time
• Independent Sets of Maximum Weight in Apple-Free Graphs

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