摘要
有向网络上的最优有向连接问题是寻求从若干起点到若干终点的连接方式,使连接费用为最小。已知此问题是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.
出处
《河南科学》
2004年第4期438-440,共3页
Henan Science
基金
国家自然科学基金资助项目(10371112)
关键词
网络优化
有向连接问题
树网络
多项式时间算法
network optimization
directed connection problem
treenetwork
polynomial algorithm