On spanning tree problems with multiple objectives

On spanning tree problems with multiple objectives

0.00 Avg rating0 Votes
Article ID: iaor1995295
Country: Switzerland
Volume: 52
Issue: 1
Start Page Number: 209
End Page Number: 230
Publication Date: Sep 1994
Journal: Annals of Operations Research
Authors:
Keywords: programming: network
Abstract:

The authors investigate two versions of multiple objective minimum spanning tree problems defined on a network with vectorial weights. First, they want to minimize the maximum of Q linear objective functions taken over the set of all spanning trees (max-linear spanning tree problem, ML-ST). Secondly, the authors look for efficient spanning trees (multi-criteria spanning tree problem, MC-ST). Problem ML-ST is shown to be NP-complete. An exact algorithm which is based on ranking is presented. The procedure can also be used as an approximation scheme. For solving the bicriterion MC-ST, which in the worst case may have an exponential number of efficient trees, a two-phase procedure is presented. Based on the computation of extremal efficient spanning trees the authors use neighbourhood search to determine a sequence of solutions with the property that the distance between two consecutive solutions is less than a given accuracy.

Reviews

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