A Lagrangian Relaxation for the Maximum Stable Set Problem

Simple item page
dc.creatorCampelo, Manoel
dc.creatorCorrea, Ricardo C.
dc.date2009-03-08
dc.date.accessioned2026-07-07T12:50:21Z
dc.date.available2026-07-07T12:50:21Z
dc.descriptionWe propose a new integer programming formulation for the problem of finding a maximum stable set of a graph based on representatives of stable sets. In addition, we investigate exact solutions provided by a Lagrangian decomposition of this formulation in which only one constraint is relaxed. Some computational experiments were carried out with an effective multi-threaded implementation of our algorithm in a multi-core system, and their results are presented.
dc.descriptionSubmitted to International Transactions on Operations Research
dc.identifierhttps://arxiv.org/abs/0903.1407
dc.identifierhttp://arxiv.org/abs/0903.1407
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/222661
dc.subjectDiscrete Mathematics
dc.subjectData Structures and Algorithms
dc.titleA Lagrangian Relaxation for the Maximum Stable Set Problem
dc.typetext

Files

Collections

arXiv