Independent Sets of Maximum Weight in Apple-Free Graphs
From MaRDI portal
Publication:5894185
DOI10.1137/090750822zbMath1211.68281MaRDI 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
polynomial-time algorithm; modular decomposition; maximum independent set; claw-free graphs; clique separators; apple-free graphs
68R10: Graph theory (including graph drawing) in computer science
05C75: Structural characterization of families of graphs
05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
Related Items
On the structure of (pan, even hole)‐free graphs, Unnamed Item, Maximum independent sets in subcubic graphs: new results, Combining decomposition approaches for the maximum weight stable set problem, 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, On atomic structure of \(P_5\)-free subclasses and maximum weight independent set problem, Set graphs. IV. Further connections with claw-freeness, Addendum to: ``Maximum weight independent sets in hole- and co-chair-free graphs, Hybrid tractability of valued constraint problems, Maximum regular induced subgraphs in \(2P_3\)-free graphs, Maximum weight independent sets in hole- and dart-free graphs, On distance-3 matchings and induced matchings, Graphs without large apples and the maximum weight independent set problem, Weighted independent sets in a subclass of \(P_6\)-free graphs, Maximum weight independent set for \(\ell\)claw-free graphs in polynomial time, Decomposition techniques applied to the clique-stable set separation problem, Scheduling algorithm to select optimal programme slots in television channels: a graph theoretic approach, Approximation of knapsack problems with conflict and forcing graphs, New results on independent sets in extensions of \(2K_2\)-free graphs, Coloring graph classes with no induced fork via perfect divisibility, On the complexity of the independent set problem in triangle graphs, On efficient domination for some classes of \(H\)-free bipartite graphs, The quadratic balanced optimization problem, A note on the Cornaz-Jost transformation to solve the graph coloring problem, Independent Sets in Classes Related to Chair-Free Graphs, Maximum Weight Independent Sets in ( $$S_{1,1,3}$$ , bull)-free Graphs
