A branch-and-bound algorithm for the mini-max spanning forest problem |
| |
| Institution: | 1. Molecular Imaging Center, National Institute of Radiological Sciences, Chiba, Japan;2. Graduate School of Engineering, Osaka Prefecture University, Sakai, Osaka, Japan;3. Laboratory of Molecular Imaging, Singapore Bioimaging Consortium, Singapore, Singapore;4. Graduate School of Science, Osaka University, Osaka, Japan;5. Department of Intractable Diseases, Research Institute, National Center for Global Health and Medicine, Tokyo, Japan;1. College of Mathematics and Informatics, South China Agricultural University, China;2. School of Data and Computer Science, Sun Yat-Sen University, China;3. School of Computer Science, University of Adelaide, Australia;1. School Of Internet Of Things Engineering, Jiangnan University, Wuxi 214122, China;2. Key Laboratory of Advanced Process Control for Light Industry Ministry of Education, Jiangnan University, Wuxi 214122, China |
| |
| Abstract: | The mini-max spanning forest problem requires to find a spanning forest of an undirected graph that minimizes the maximum of the costs of constituent trees. In a previous work we proved this problem NP-hard. In the current paper we present three lower bounds for this problem and develop a branch-and-bound algorithm to solve the problem exactly. The algorithm is implemented and numerical experiments are conducted on a series of test problems. The experiments compare the performances of the proposed bounds and search strategies in the algorithm as well as investigate the effects of instance characteristics on the behavior of the algorithm. Also, extension of the problem to the case of more than two root vertices as well as to the problem of determining the root locations are discussed. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
