In this paper, two problems derived from reload problems in transport logistics are introduced and studied. Given a transitive digraph
G=(V,A,w) with nonnegative arc weights (the transport network) and a set of directed node pairs
B (the demand), the objective of the Steiner Diagram Problem is to find an acyclic set of arcs
S of minimum cost that contains a directed path for each pair in
B. This problem is
![]()
-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. A special case of this problem is a weighted edge cover problem with
k cost functions on the vertices. It is shown that this problem is
![]()
-complete for
k![]()
3. An efficient algorithm for the case
k=2 is given.
