A combined parallel Lagrangian decomposition and cutting-plane generation for maximum stable set problems

DOI10.1016/J.ENDM.2010.05.064MaRDI QIDQ2883604zbMATH OpenOpenAlexFDO

Authors Ricardo C. Corrêa, Manoel Campêlo

Publication date 13 May 2012

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

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

zbMATH Keywords

graphsinteger programmingLagrangian decompositionstable sets

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Integer programming (90C10)

Recommendations

• A branch-and-cut algorithm for the maximum cardinality stable set problem
• A branch and cut solver for the maximum stable set problem
• An exact algorithm for the maximum stable set problem
• A tutorial on branch and cut algorithms for the maximum stable set problem
• On the separation of topology-free rank inequalities for the max stable set problem

Cites work

• scientific article; zbMATH DE number 1256635 (Why is no real title available?)
• scientific article; zbMATH DE number 956868 (Why is no real title available?)
• A branch-and-cut algorithm for equitable coloring based on a formulation by representatives
• A branch-and-cut algorithm for graph coloring
• A branch-and-cut algorithm for the maximum cardinality stable set problem
• A class representative model for pure parsimony haplotyping
• Cliques, holes and the vertex coloring polytope
• Conflict graphs in solving integer programming problems
• On the asymmetric representatives formulation for the vertex coloring problem
• Polyhedral results for the bipartite induced subgraph problem

Cited in

(4)

• The Maximum k-Colorable Subgraph Problem and Related Problems
• Mathematical programming models and exact algorithms
• The strength of Dantzig-Wolfe reformulations for the stable set and related problems
• Characterization of QUBO reformulations for the maximum \(k\)-colorable subgraph problem

This page was built for publication: A combined parallel Lagrangian decomposition and cutting-plane generation for maximum stable set problems

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