Solving the 2-rooted mini-max spanning forest problem by branch-and-bound |
| |
| Authors: | M Mekking A Volgenant |
| |
| Institution: | Operations Research Group, Faculty of Economics and Econometrics, University of Amsterdam, Roetersstraat 11, 1018 WB Amsterdam, The Netherlands |
| |
| Abstract: | The 2-rooted mini-max spanning forest problem is to find a spanning forest with two given root nodes on an undirected graph, such that the maximum tree cost in this forest is minimized. We introduce a branch-and-bound algorithm based on selecting nodes. On test instances up to 50 nodes the algorithm gives much better computational results than a known algorithm that is based on selecting edges. Furthermore the new algorithm can easily solve problem instances up to 80 nodes. |
| |
| Keywords: | Combinatorial optimization Branch-and-bound Spanning forest Bottleneck criterion |
| 本文献已被 ScienceDirect 等数据库收录！ |
