A Combined Parallel Lagrangian Decomposition and Cutting-Plane Generation for Maximum Stable Set Problems

DOI10.1016/j.endm.2010.05.064zbMath1237.90241OpenAlexW1985136662MaRDI QIDQ2883604

Ricardo C. Corrêa, Manoel B. 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

integer programminggraphsLagrangian decompositionstable sets

Mathematics Subject Classification ID

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

Related Items (4)

Mathematical Programming Models and Exact Algorithms ⋮ The Maximum k-Colorable Subgraph Problem and Related Problems ⋮ The strength of Dantzig-Wolfe reformulations for the stable set and related problems ⋮ Characterization of QUBO reformulations for the maximum \(k\)-colorable subgraph problem

Cites Work

• Unnamed Item
• Unnamed Item
• Cliques, holes and the vertex coloring polytope
• Conflict graphs in solving integer programming problems
• Polyhedral results for the bipartite induced subgraph problem
• On the asymmetric representatives formulation for the vertex coloring problem
• A branch-and-cut algorithm for graph coloring
• A Branch-and-Cut Algorithm for Equitable Coloring based on a Formulation by Representatives
• A Class Representative Model for Pure Parsimony Haplotyping
• A branch-and-cut algorithm for the maximum cardinality stable set problem

This page was built for publication: A Combined Parallel Lagrangian Decomposition and Cutting-Plane Generation for Maximum Stable Set Problems