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

  • Export nach Bibtex
  • Export nach RIS

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 / 51 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

$Rev: 13581 $