Name
Abstract | ||
|---|---|---|
In this paper, we show a branch-and-cut approach to solve the minimum spanning tree problem with conflicting edge pairs. This is a NP-hard variant of the classical minimum spanning tree problem, in which there are mutually exclusive edges. We introduce a new set of valid inequalities for the problem, based on the properties of its feasible solutions, and we develop a branch-and-cut algorithm based on them. Computational tests are performed both on benchmark instances coming from the literature and on some newly proposed ones. Results show that our approach outperforms a previous branch-and-cut algorithm proposed for the same problem. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1007/s10479-018-2895-y | Annals of Operations Research |
Keywords | DocType | Volume |
Minimum spanning tree, Conflicting edges, Branch-and-cut | Journal | 298 |
Issue | ISSN | Citations |
1 | 1572-9338 | 1 |
PageRank | References | Authors |
0.36 | 9 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Francesco Carrabs | 1 | 199 | 15.55 |
| R. Cerulli | 2 | 252 | 23.85 |
| Rosa Pentangelo | 3 | 1 | 0.36 |
| A. Raiconi | 4 | 131 | 9.68 |