Name
Title | ||
|---|---|---|
A primal branch-and-cut algorithm for the degree-constrained minimum spanning tree problem |
Abstract | ||
|---|---|---|
The degree-constrained minimum spanning tree (DCMST) is relevant in the design of networks. It consists of finding a spanning tree whose nodes do not exceed a given maximum degree and whose total edge length is minimum. We design a primal branch-and-cut algorithm that solves instances of the problem to optimality. Primal methods have not been used extensively in the past, and their performance often could not compete with their standard 'dual' counterparts. We show that primal separation procedures yield good bounds for the DCMST problem. On several instances, the primal branch-and-cut program turns out to be competitive with other methods known in the literature. This shows the potential of the primal method. |
Year | Venue | Keywords |
|---|---|---|
2007 | WEA | maximum degree,primal branch-and-cut program,primal method,good bound,tree problem,total edge length,dcmst problem,primal branch-and-cut algorithm,degree-constrained minimum,primal separation procedure |
Field | DocType | Volume |
Expected linear time MST algorithm,Combinatorics,Mathematical optimization,Distributed minimum spanning tree,Branch and cut,Euclidean minimum spanning tree,Spanning tree,Reverse-delete algorithm,Kruskal's algorithm,Mathematics,Minimum spanning tree | Conference | 4525 |
ISSN | Citations | PageRank |
0302-9743 | 0 | 0.34 |
References | Authors | |
9 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| markus behle | 1 | 34 | 2.43 |
| Michael Jünger | 2 | 1194 | 393.00 |
| Frauke Liers | 3 | 60 | 8.89 |