Independent sets of maximum weight in apple-free graphs

DOI10.1137/090750822MaRDI QIDQ5894185zbMATH OpenOpenAlexFDO

Authors Andreas Brandstädt, Raffaele Mosca, Vadim 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

modular decompositionpolynomial-time algorithmmaximum independent setclaw-free graphsclique separatorsapple-free graphs

Mathematics Subject Classification ID

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

Recommendations

• Independent Sets of Maximum Weight in Apple-Free Graphs
• On independent vertex sets in subclasses of apple-free graphs
• Graphs without large apples and the maximum weight independent set problem
• Polynomial-time algorithm for maximum weight independent set on \(P_6\)-free graphs
• A polynomial algorithm to find an independent set of maximum weight in a fork-free graph

Cited in

(34)

• Approximation of knapsack problems with conflict and forcing graphs
• A faster algorithm for maximum independent set on interval filament graphs
• Set graphs. IV. Further connections with claw-freeness
• On independent vertex sets in subclasses of apple-free graphs
• Graphs without large apples and the maximum weight independent set problem
• On efficient domination for some classes of H-free bipartite graphs
• Maximum weight t-sparse set problem on vector-weighted graphs
• Maximum regular induced subgraphs in 2P₃-free graphs
• Hybrid tractability of valued constraint problems
• Maximum weighted independent sets on transitive graphs and applications
• 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
• On atomic structure of \(P_5\)-free subclasses and maximum weight independent set problem
• New results on independent sets in extensions of \(2K_2\)-free graphs
• A note on the Cornaz-Jost transformation to solve the graph coloring problem
• Maximum weight independent sets in hole- and dart-free graphs
• Maximum Weight Independent Sets in ( $$S_{1,1,3}$$ , bull)-free Graphs
• A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
• Weighted independent sets in a subclass of P₆-free graphs
• On the complexity of the independent set problem in triangle graphs
• Coloring graph classes with no induced fork via perfect divisibility
• Independent sets and vertex covers considered within the context of robust optimization
• Scheduling algorithm to select optimal programme slots in television channels: a graph theoretic approach
• Addendum to: ``Maximum weight independent sets in hole- and co-chair-free graphs
• A sufficient condition to extend polynomial results for the maximum independent set problem
• On distance-3 matchings and induced matchings
• Independent Sets of Maximum Weight in Apple-Free Graphs
• On the structure of (pan, even hole)-free graphs
• Maximum weight independent set for claw-free graphs in polynomial time
• Independent Sets in Classes Related to Chair-Free Graphs
• Decomposition techniques applied to the clique-stable set separation problem
• Induced subgraphs of bounded treewidth and the container method
• The quadratic balanced optimization problem

This page was built for publication: Independent sets of maximum weight in apple-free graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5894185)