Independent Sets of Maximum Weight in Apple-Free Graphs

DOI10.1137/090750822zbMath1211.68281OpenAlexW1967799084MaRDI QIDQ5894185

Andreas Brandstädt, Raffaele Mosca, Vadim V. Lozin

Publication date: 15 March 2011

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: http://wrap.warwick.ac.uk/3314/1/WRAP_Lozin_independent_sets.pdf

zbMATH Keywords

polynomial-time algorithmmodular decompositionmaximum independent setclaw-free graphsclique separatorsapple-free graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Structural characterization of families of graphs (05C75) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (29)

Weighted independent sets in classes of \(P_6\)-free graphs ⋮ Maximum weight independent sets in classes related to claw-free graphs ⋮ A sufficient condition to extend polynomial results for the maximum independent set problem ⋮ New results on independent sets in extensions of \(2K_2\)-free graphs ⋮ Coloring graph classes with no induced fork via perfect divisibility ⋮ On atomic structure of \(P_5\)-free subclasses and maximum weight independent set problem ⋮ Combining decomposition approaches for the maximum weight stable set problem ⋮ Set graphs. IV. Further connections with claw-freeness ⋮ Maximum weight t-sparse set problem on vector-weighted graphs ⋮ Maximum weight independent set for \(\ell\)claw-free graphs in polynomial time ⋮ On the structure of (pan, even hole)‐free graphs ⋮ Weighted independent sets in a subclass of \(P_6\)-free graphs ⋮ Decomposition techniques applied to the clique-stable set separation problem ⋮ Hybrid tractability of valued constraint problems ⋮ A note on the Cornaz-Jost transformation to solve the graph coloring problem ⋮ Addendum to: ``Maximum weight independent sets in hole- and co-chair-free graphs ⋮ Maximum regular induced subgraphs in \(2P_3\)-free graphs ⋮ Approximation of knapsack problems with conflict and forcing graphs ⋮ Maximum weight independent sets in hole- and dart-free graphs ⋮ On distance-3 matchings and induced matchings ⋮ On the complexity of the independent set problem in triangle graphs ⋮ Independent Sets in Classes Related to Chair-Free Graphs ⋮ Scheduling algorithm to select optimal programme slots in television channels: a graph theoretic approach ⋮ Unnamed Item ⋮ Graphs without large apples and the maximum weight independent set problem ⋮ Maximum independent sets in subcubic graphs: new results ⋮ Maximum Weight Independent Sets in ( $$S_{1,1,3}$$ , bull)-free Graphs ⋮ On efficient domination for some classes of \(H\)-free bipartite graphs ⋮ The quadratic balanced optimization problem

This page was built for publication: Independent Sets of Maximum Weight in Apple-Free Graphs