On spanning tree problems with multiple objectives |
| |
Authors: | Horst W. Hamacher Günter Ruhe |
| |
Affiliation: | (1) Fachbereich Mathematik, and Zentrum für Techno-und Wirtschaftsmathematik, Universität Kaiserslautern, Kaiserslautern, Germany |
| |
Abstract: | 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 ofQ 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.Partially supported by Deutsche Forschungsgemeinschaft and HCº Contract no. ERBCHRXCT 930087.Partially supported by Alexander von Humboldt-Stiftung. |
| |
Keywords: | Multiple objective max-linear multi-criteria networks spanning trees algorithms |
本文献已被 SpringerLink 等数据库收录! |
|