TY - RPRT
A1 - Hamacher, Horst W.
A1 - Ruhe, Günther
T1 - On spanning tree problems with multiple objectives
N2 - We investigate two versions of multiple objective minimum spanning tree
problems defined on a network with vectorial weights. First, we 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, we 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 we 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.
T3 - Preprints (rote Reihe) des Fachbereich Mathematik - 239
Y1 - 1993
UR - https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4857
UR - https://nbn-resolving.org/urn:nbn:de:hbz:386-kluedo-48571
ER -