Abstract | ||
---|---|---|
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. |
Year | Venue | Keywords |
---|---|---|
2009 | Computing Research Repository | stable set,data structure,lagrangian relaxation,discrete mathematics,exact solution,computer experiment |
Field | DocType | Volume |
Stable set problem,Graph,Discrete mathematics,Combinatorics,Integer programming,Independent set,Lagrangian decomposition,Lagrangian relaxation,Mathematics | Journal | abs/0903.1407 |
Citations | PageRank | References |
2 | 0.40 | 16 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Manoel B. Campêlo | 1 | 151 | 19.59 |
Ricardo C. Corrêa | 2 | 207 | 18.74 |