A Lagrangian Relaxation for the Maximum Stable Set Problem

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

We 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.
Submitted to International Transactions on Operations Research

Keywords

Discrete Mathematics, Data Structures and Algorithms

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/222661

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/0903.1407
 http://arxiv.org/abs/0903.1407

Collections

arXiv