A polyhedral study of the maximum stable set problem with weights on vertex-subsets

DOI10.1016/J.DAM.2015.05.032MaRDI QIDQ299097zbMATH OpenOpenAlexFDO

Authors Victor Campos, Ricardo C. Corrêa, Diego Delle Donne, Javier Marenco, Marcelo Mydlarz, Manoel Campêlo

Publication date 22 June 2016

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2015.05.032

zbMATH Keywords

integer programmingmaximum stable set

Mathematics Subject Classification ID

Integer programming (90C10) Signed and weighted graphs (05C22)

Recommendations

• Bounded Stable Sets: Polytopes and Colorings
• A polyhedral investigation of star colorings
• Solving vertex coloring problems as maximum weight stable set problems
• Fixed cardinality stable sets
• Theoretical Computer Science

Cites work

• scientific article; zbMATH DE number 1786225 (Why is no real title available?)
• A Column Generation Approach for Graph Coloring
• A branch-and-cut algorithm for the maximum cardinality stable set problem
• A fast algorithm for the maximum clique problem
• An exact approach for the vertex coloring problem
• Maximum-weight stable sets and safe lower bounds for graph coloring
• On the asymmetric representatives formulation for the vertex coloring problem
• Set covering and packing formulations of graph coloring: Algorithms and first polyhedral results

Cited in

(1)

• Combining decomposition approaches for the maximum weight stable set problem

This page was built for publication: A polyhedral study of the maximum stable set problem with weights on vertex-subsets

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