KLUEDO RSS FeedKLUEDO Dokumente/documents
https://kluedo.ub.uni-kl.de/index/index/
Thu, 21 Jun 2007 22:56:38 +0200Thu, 21 Jun 2007 22:56:38 +0200Weight-Constrained Minimum Spanning Tree Problem
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1873
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.Sebastian Tobias Henndiplomhttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1873Thu, 21 Jun 2007 22:56:38 +0200Minimum Fundamental Cut Basis Problem
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1675
Any tree in an undirected graph defines a fundamental cut basis. The minimum fundamental cut basis problem is to find a tree minimizing the weight of the corresponding basis. This problem is NP, in the thesis heuristics, relaxations, and numerical results are presented.Anne Schwahndiplomhttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1675Wed, 26 Oct 2005 16:08:26 +0200