- Solving the 2-rooted mini-max spanning forest problem by branch-and-bound
- European Journal of Operational Research
- Volume | Issue number
- 203 | 1
- Pages (from-to)
- Document type
- Faculty of Economics and Business (FEB)
- Amsterdam School of Economics Research Institute (ASE-RI)
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.
We consider some alternative and polynomial criteria. Finally we discuss some generalizations, e.g., the problem without given root nodes, i.e., the root nodes have to be chosen.
- go to publisher's site
If you believe that digital publication of certain material infringes any of your rights or (privacy) interests, please let the Library know, stating your reasons. In case of a legitimate complaint, the Library will make the material inaccessible and/or remove it from the website. Please Ask the Library, or send a letter to: Library of the University of Amsterdam, Secretariat, Singel 425, 1012 WP Amsterdam, The Netherlands. You will be contacted as soon as possible.