The Exact Weighted Independent Set Problem in Perfect Graphs and Related Classes

DOI10.1016/j.endm.2009.11.052zbMath1268.05152OpenAlexW2010669807MaRDI QIDQ2840556

Jérôme Monnot, Martin Milanič

Publication date: 19 July 2013

Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.endm.2009.11.052

zbMATH Keywords

complexitymaximum weight independent set problemvertex-weighted graphcomplete subset sum problemexact weighted independent set problemindependent set of given weight

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (3)

Knapsack problem with objective value gaps ⋮ Simple paths with exact and forbidden lengths ⋮ A weighted perfect matching with constraints on weights of its parts

Cites Work

• Unnamed Item
• Unnamed Item
• Efficient robust algorithms for the maximum weight stable set problem in chair-free graph classes
• A unified approach to domination problems on interval graphs
• Algorithmic graph theory and perfect graphs
• Linear time solvable optimization problems on graphs of bounded clique-width
• The complexity of restricted spanning tree problems
• Graph Classes: A Survey
• Paths, Trees, and Flowers

This page was built for publication: The Exact Weighted Independent Set Problem in Perfect Graphs and Related Classes