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.

Actions:

Download:	Postscript - Preprinted Version Download (294kB) | Preview
Editorial actions:	View Item (Login required)