Steiner-Diagrams and k-Star-Hubs
Blasum, Ulrich and Hochstättler, Winfried and Oertel, Peter and Woeginger, Gerhard J.
(2007)
Steiner-Diagrams and k-Star-Hubs.
Published in:
Journal of Discrete Algorithms Vol. 5 (3).
pp. 622-634.
Abstract
In this report, we introduce and study two problems derived from reload problems in transport logistics. Given a transitive digraph G=(V,A,w) with non-negative edge-weights and a set of demand edges B, the objective of the Steiner-diagram-problem is to find an acyclic set of edges S of minimal cost, whose transitive closure contains B. This problem is NP-complete in the general case and has some interesting structural properties that make it polynomially solvable if the size of B is bounded by a constant, the triangle inequality holds in A and A is transitively closed. Secondly, we discuss a weighted edge-cover problem with k cost functions on the vertices and give an efficient algorithm for the case k = 2. This report is an extended version of 99-342.
Download: |
Download (294kB) | Preview |
---|---|
Editorial actions: | ![]() |
Item Type: | Article |
---|---|
Citations: | 0 (Google Scholar) | |
Uncontrolled Keywords: | computational complexity min-cost flow NP-completeness Steiner arborescence Steiner diagram Steiner tree vehicle routing |
Subjects: | |
Divisions: | Institute of Computer Science > Computer Science Department - Prof. Dr. Schrader Mathematical Institute > Prof. Dr. Faigle |
Related URLs: |
ZAIK Number: | zaik2000-384 |
---|---|
Depositing User: | Ulrich Blasum |
Date Deposited: | 29 May 2007 00:00 |
Last Modified: | 09 Jan 2012 16:49 |
URI: | http://e-archive.informatik.uni-koeln.de/id/eprint/384 |