UNIVERSITÄTSBIBLIOTHEK

On spanning tree problems with multiple objectives

  • 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.

Metadaten exportieren

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar
Metadaten
Verfasserangaben:Horst W. Hamacher, Günther Ruhe
URN (Permalink):urn:nbn:de:hbz:386-kluedo-48571
Schriftenreihe (Bandnummer):Preprints (rote Reihe) des Fachbereich Mathematik (239)
Dokumentart:Bericht
Sprache der Veröffentlichung:Englisch
Veröffentlichungsdatum (online):16.10.2017
Jahr der Veröffentlichung:1993
Veröffentlichende Institution:Technische Universität Kaiserslautern
Datum der Publikation (Server):16.10.2017
Seitenzahl:28
Fachbereiche / Organisatorische Einheiten:Fachbereich Mathematik
DDC-Sachgruppen:5 Naturwissenschaften und Mathematik / 510 Mathematik
Lizenz (Deutsch):Creative Commons 4.0 - Namensnennung, nicht kommerziell, keine Bearbeitung (CC BY-NC-ND 4.0)