Blasum, Ulrich and Hochstättler, Winfried and Oertel, Peter (1999) Steiner-Diagrams.
Technical Report , 8 p.


In this report, we introduce and study the Steiner-diagram-problem. Given a digraph G=(V,A,w) with non-negative edge-weights and a set of demand edges B, the objective is to find an acyclic set of edges of minimal cost, whose transitive closure contains B. We will show that this problem is NP-complete in the general case and that it is polynomially solvable if the size of B is bounded by a constant.

Download: [img] Postscript
Download (216kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik1999-342
Depositing User: Ulrich Blasum
Date Deposited: 02 Apr 2001 00:00
Last Modified: 16 Jan 2012 14:46