### Abstract

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.

Original language | English |
---|---|

Pages (from-to) | 622-634 |

Journal | Journal of Discrete Algorithms |

Volume | 5 |

Issue number | 3 |

DOIs | |

Publication status | Published - 2007 |

## Fingerprint Dive into the research topics of 'Steiner diagrams and $k$-star hubs'. Together they form a unique fingerprint.

## Cite this

Blasum, U., Hochstättler, W., Oertel, P., & Woeginger, G. J. (2007). Steiner diagrams and $k$-star hubs.

*Journal of Discrete Algorithms*,*5*(3), 622-634. https://doi.org/10.1016/j.jda.2006.06.001