Edge exchanges in the degree-constrained minimum spanning tree problem (Q1086497)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Edge exchanges in the degree-constrained minimum spanning tree problem |
scientific article; zbMATH DE number 3985001
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Edge exchanges in the degree-constrained minimum spanning tree problem |
scientific article; zbMATH DE number 3985001 |
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
0 references
0.89227146
0 references
0.8893919
0 references
0.8880881
0 references
0.88384706
0 references
0.88229775
0 references
0.88094735
0 references
0.88032913
0 references
0.87997544
0 references
0.8788477
0 references
0.8783498
0 references
