KLUEDO RSS FeedKLUEDO Dokumente/documents
https://kluedo.ub.uni-kl.de/index/index/
Thu, 19 Oct 2017 08:33:04 +0200Thu, 19 Oct 2017 08:33:04 +0200Weighted k-cardinality trees
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4883
We consider the k -CARD TREE problem, i.e., the problem of finding in a given undirected graph G a subtree with k edges, having minimum weight. Applications of this problem arise in oil-field leasing and facility layout. While the general problem is shown to be strongly NP hard, it can be solved in polynomial time if G is itself a tree. We give an integer programming formulation of k-CARD TREE, and an efficient exact separation routine for a set of generalized subtour elimination constraints. The polyhedral structure of the convex huLl of the integer solutions is studied.Matteo Fischetti; Horst W. Hamacher; Kurt Jörnsten; Francesco Maffiolireporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/4883Thu, 19 Oct 2017 08:33:04 +0200Minimum Cut Bases in Undirected Networks
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1857
Given an undirected, connected network G = (V,E) with weights on the edges, the cut basis problem is asking for a maximal number of linear independent cuts such that the sum of the cut weights is minimized. Surprisingly, this problem has not attained as much attention as its graph theoretic counterpart, the cycle basis problem. We consider two versions of the problem, the unconstrained and the fundamental cut basis problem. For the unconstrained case, where the cuts in the basis can be of an arbitrary kind, the problem can be written as a multiterminal network flow problem and is thus solvable in strongly polynomial time. The complexity of this algorithm improves the complexity of the best algorithms for the cycle basis problem, such that it is preferable for cycle basis problems in planar graphs. In contrast, the fundamental cut basis problem, where all cuts in the basis are obtained by deleting an edge, each, from a spanning tree T is shown to be NP-hard. We present heuristics, integer programming formulations and summarize first experiences with numerical tests.Florentine Bunke; Horst W. Hamacher; Francesco Maffioli; Anne Schwahnpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1857Thu, 26 Apr 2007 16:10:59 +0200