The exact weighted independent set problem in perfect graphs and related classes

DOI10.1016/J.ENDM.2009.11.052MaRDI QIDQ2840556zbMATH OpenOpenAlexFDO

Authors Martin Milanič, Jérôme Monnot

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

complete subset sum problemcomplexityexact weighted independent set problemindependent set of given weightmaximum weight independent set problemvertex-weighted graph

Mathematics Subject Classification ID

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

Recommendations

• The weighted maximum independent set problem in permutation graphs
• scientific article; zbMATH DE number 4064507
• Exact algorithms for maximum weighted independent set on sparse graphs (extended abstract)
• Maximum weightk-independent set problem on permutation graphs
• Weighted independent perfect domination on cocomparability graphs
• Exactly solving the maximum weight independent set problem on large real-world graphs
• Weighted independent sets in a subclass of P₆-free graphs
• Maximum weighted independent sets on transitive graphs and applications
• Weighted independent sets in classes of \(P_6\)-free graphs
• Efficient computation of tolerances in the weighted independent set problem for some classes of graphs

Cites work

• A unified approach to domination problems on interval graphs
• Algorithmic graph theory and perfect graphs
• Efficient robust algorithms for the maximum weight stable set problem in chair-free graph classes
• Graph Classes: A Survey
• scientific article; zbMATH DE number 3882470 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Linear time solvable optimization problems on graphs of bounded clique-width
• Paths, Trees, and Flowers
• The complexity of restricted spanning tree problems

Cited in

(7)

• The weighted perfect domination problem and its variants
• Typical values of extremal-weight combinatorial structures with independent symmetric weights
• Knapsack problem with objective value gaps
• Simple paths with exact and forbidden lengths
• Efficient computation of tolerances in the weighted independent set problem for some classes of graphs
• A weighted perfect matching with constraints on weights of its parts
• Tight bounds for budgeted maximum weight independent set in bipartite and perfect graphs

This page was built for publication: The exact weighted independent set problem in perfect graphs and related classes

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