کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
430989 | 688239 | 2007 | 13 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Steiner diagrams and k-star hubs Steiner diagrams and k-star hubs](/preview/png/430989.png)
In this paper, two problems derived from reload problems in transport logistics are introduced and studied. Given a transitive digraph G=(V,A,w)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 NPNP-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 NPNP-complete for k⩾3k⩾3. An efficient algorithm for the case k=2k=2 is given.
Journal: Journal of Discrete Algorithms - Volume 5, Issue 3, September 2007, Pages 622–634