Independent Sets of Maximum Weight in Apple-Free Graphs

DOI10.1007/978-3-540-92182-0_74zbMath1183.05076OpenAlexW2172358501MaRDI QIDQ5901364

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

Publication date: 29 January 2009

Published in: Algorithms and Computation (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

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (5)

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 ⋮ Maximum weight independent set for \(\ell\)claw-free graphs in polynomial time ⋮ Complexity results for equistable graphs and related classes ⋮ On Distance-3 Matchings and Induced Matchings

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