Name
Abstract | ||
|---|---|---|
This paper develops a greedy heuristic for the capacitated minimum spanning tree problem (CMSTP), based on the two widely known methods of Prim and of Esau–Williams. The proposed algorithm intertwines two-stages: an enhanced combination of the Prim and Esau–Williams approaches via augmented and synthetic node selection criteria, and an increase of the feasible solution space by perturbing the input data using the law of cosines. Computational tests on benchmark problems show that the new heuristic provides extremely good performance results for the CMSTP, justifying its effectiveness and robustness. Furthermore, excluding the feasible space expansion, we show that we can still obtain good quality solutions in very short computational times. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1057/s41274-016-0146-7 | JORS |
Keywords | Field | DocType |
capacitated minimum spanning tree problem, Esau-Williams heuristic, Prim’s algorithm | Capacitated minimum spanning tree,Mathematical optimization,Heuristic,Distributed minimum spanning tree,Computer science,Prim's algorithm,Algorithm,Greedy algorithm,Spanning tree,Kruskal's algorithm,Minimum spanning tree | Journal |
Volume | Issue | ISSN |
68 | 10 | 0160-5682 |
Citations | PageRank | References |
1 | 0.36 | 20 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Manolis N. Kritikos | 1 | 9 | 2.59 |
| George Ioannou | 2 | 106 | 11.99 |