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.

Download full text files

Export metadata

Additional Services

Search Google Scholar
Metadaten
Author:Sebastian Tobias Henn
URN:urn:nbn:de:hbz:386-kluedo-14950
Document Type:Diploma Thesis
Language of publication:English
Year of Completion:2007
Year of first Publication:2007
Publishing Institution:Technische Universität Kaiserslautern
Granting Institution:Technische Universität Kaiserslautern
Date of the Publication (Server):2007/06/21
Tag:adjacency relations; combinatorial optimization; knapsack; minimal spanning tree
GND Keyword:Minimal spannender Baum; Knapsack; Kombinatorische Optimierung; Adjazenz-Beziehungen
Faculties / Organisational entities:Kaiserslautern - Fachbereich Mathematik
DDC-Cassification:5 Naturwissenschaften und Mathematik / 510 Mathematik
MSC-Classification (mathematics):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
Licence (German):Standard gemäß KLUEDO-Leitlinien vor dem 27.05.2011