Name
Title | ||
|---|---|---|
The minimum connected dominating set problem: formulation, valid inequalities and a branch-and-cut algorithm |
Abstract | ||
|---|---|---|
We consider the minimum connected dominating set problem. We present an integer programming formulation and new valid inequalities. A branchand-cut algorithm based on the reinforced formulation is also provided. Computational results indicate that the reinforced lower bounds are always stronger than the bounds implied by the formulation from which resulted one of the best known exact algorithms for the problem. In some cases, the reinforced lower bounds are stronger than those implied by the strongest known formulation to date. For dense graphs, our algorithm provides the best results in the literature. For sparse instances, known to be harder, our method is outperformed by another one. We discuss reasons for that and how to improve our current computational results. One possible way to achieve such goals is to devise specific separation algorithms for some classes of valid inequalities introduced here. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1007/978-3-642-21527-8_21 | INOC |
Keywords | Field | DocType |
computational result,integer programming formulation,branchand-cut algorithm,best result,branch-and-cut algorithm,new valid inequality,strongest known formulation,lower bound,exact algorithm,current computational result,specific separation algorithm | Discrete mathematics,Graph,Combinatorics,Exact algorithm,Branch and cut,Algorithm,Inequality,Integer programming,Connected dominating set,Separation algorithm,Mathematics | Conference |
Volume | ISSN | Citations |
6701 | 0302-9743 | 13 |
PageRank | References | Authors |
0.74 | 8 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Luidi Simonetti | 1 | 152 | 15.82 |
| Alexandre Salles da Cunha | 2 | 242 | 22.32 |
| Abilio Lucena | 3 | 362 | 34.05 |