Edge exchanges in the degree-constrained minimum spanning tree problem (Q1086497): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claim: author (P16): Item:Q163010 |
||
| Property / author | |||
| Property / author: Savelsbergh, Martin W. P. / rank | |||
Revision as of 22:28, 9 February 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Edge exchanges in the degree-constrained minimum spanning tree problem |
scientific article |
Statements
Edge exchanges in the degree-constrained minimum spanning tree problem (English)
0 references
1985
0 references
We describe a branch and bound algorithm to solve the degree-constrained minimum spanning tree problem. We propose an edge exchange analysis frequently used in the algorithm and three types of heuristic methods. Computational results are reported for problems with up to 200 vertices. These results are much better than known results from the literature.
0 references
branch and bound
0 references
degree-constrained minimum spanning tree problem
0 references
edge exchange analysis
0 references
Computational results
0 references
