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.


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: [img] Postscript - Preprinted Version
Download (294kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik2000-384
Depositing User: Ulrich Blasum
Date Deposited: 29 May 2007 00:00
Last Modified: 09 Jan 2012 16:49