A branch-and-bound algorithm for the mini-max spanning forest problem

A branch-and-bound algorithm for the mini-max spanning forest problem

0.00 Avg rating0 Votes
Article ID: iaor19991980
Country: Netherlands
Volume: 101
Issue: 1
Start Page Number: 93
End Page Number: 103
Publication Date: Aug 1997
Journal: European Journal of Operational Research
Authors: , ,
Keywords: programming: linear
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.

Reviews

Required fields are marked *. Your email address will not be published.