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

DOI10.1016/J.DAM.2015.05.032zbMATH Open1339.05167OpenAlexW626430230MaRDI QIDQ299097FDOQ299097

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

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

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

zbMATH Keywords

integer programmingmaximum stable set

Mathematics Subject Classification ID

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

Cites Work

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

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)