树网络上的最优有向连接问题

An optimal directed connection problem in tree networks

有向网络上的最优有向连接问题是寻求从若干起点到若干终点的连接方式,使连接费用为最小。已知此问题是NP-困难问题。目前的一个研究方向是探讨存在多项式时间算法的特殊情形。本文研究了这样的特殊情形:树网络上所有起点处于同一条路上,建立了多项式时间算法。

The optimal connection problem in directed networks is to find a connection scheme from some of sources to several given sinks, such that the cost of connection is minimized. It is known that this problem is NP-hard. A current direction of study is to investigate special cases with polynomial-time algorithms. In this paper we study such a special case: a tree network with all sources on a path and we present its polynomial-time algorithms.