TY - JOUR
T1 - Steiner diagrams and $k$-star hubs
AU - Blasum, U.
AU - Hochstättler, W.
AU - Oertel, P.
AU - Woeginger, G.J.
PY - 2007
Y1 - 2007
N2 - 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 k3. An efficient algorithm for the case k=2 is given.
AB - 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 k3. An efficient algorithm for the case k=2 is given.
U2 - 10.1016/j.jda.2006.06.001
DO - 10.1016/j.jda.2006.06.001
M3 - Article
VL - 5
SP - 622
EP - 634
JO - Journal of Discrete Algorithms
JF - Journal of Discrete Algorithms
SN - 1570-8667
IS - 3
ER -