UNIVERSITÄTSBIBLIOTHEK

Weight-Constrained Minimum Spanning Tree Problem

  • In an undirected graph G we associate costs and weights to each edge. The weight-constrained minimum spanning tree problem is to find a spanning tree of total edge weight at most a given value W and minimum total costs under this restriction. In this thesis a literature overview on this NP-hard problem, theoretical properties concerning the convex hull and the Lagrangian relaxation are given. We present also some in- and exclusion-test for this problem. We apply a ranking algorithm and the method of approximation through decomposition to our problem and design also a new branch and bound scheme. The numerical results show that this new solution approach performs better than the existing algorithms.
  • In einem ungerichteten Graphen G weisen wird jeder Kante Kosten und ein Gewicht zugewiesen. Das Weight-constrained Minimum Spanning Tree Problem ist einen spannenden Baum zu finden, dessen Gewicht kleiner einem Wert W ist und unter dieser Bedinungen kostenminimal ist. Die Arbeit enthält einen Literatur Überblick über dieses NP-schwere Problem sowie thereotische Eigenschaften über die konvexe Hülle und die Lagrange Relaxierung. Des Weiteren werden In- und Exklusionen für dieses Problem vorgestellt. Weiterhin wird ein Ranking-Algorithmus und eine Dekompositionsmethode, sowie ein neuer Branch- and Bound-Ansatz auf das Problem angewandt. In den numerischen Test erzielt dieser Algorithmus bessere Resultate als die existierenden Algorithmen.

Volltext Dateien herunterladen

Metadaten exportieren

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar
Metadaten
Verfasserangaben:Sebastian Tobias Henn
URN (Permalink):urn:nbn:de:hbz:386-kluedo-14950
Dokumentart:Diplomarbeit
Sprache der Veröffentlichung:Englisch
Jahr der Fertigstellung:2007
Jahr der Veröffentlichung:2007
Veröffentlichende Institution:Technische Universität Kaiserslautern
Titel verleihende Institution:Technische Universität Kaiserslautern
Datum der Publikation (Server):21.06.2007
Freies Schlagwort / Tag:adjacency relations; combinatorial optimization; knapsack; minimal spanning tree
GND-Schlagwort:Adjazenz-Beziehungen; Knapsack; Kombinatorische Optimierung; Minimal spannender Baum
Fachbereiche / Organisatorische Einheiten:Fachbereich Mathematik
DDC-Sachgruppen:5 Naturwissenschaften und Mathematik / 510 Mathematik
MSC-Klassifikation (Mathematik):05-XX COMBINATORICS (For finite fields, see 11Txx) / 05Cxx Graph theory (For applications of graphs, see 68R10, 81Q30, 81T15, 82B20, 82C20, 90C35, 92E10, 94C15) / 05C05 Trees
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C27 Combinatorial optimization
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
Lizenz (Deutsch):Standard gemäß KLUEDO-Leitlinien vor dem 27.05.2011