| 树网络上的最优有向连接问题 |
| |
| 引用本文： | 林浩,万建军. 树网络上的最优有向连接问题[J]. 河南科学, 2004, 22(4): 438-440 |
| |
| 作者姓名： | 林浩 万建军 |
| |
| 作者单位： | 郑州工程学院数理系,河南,郑州,450052;郑州工程学院数理系,河南,郑州,450052 |
| |
| 基金项目： | 国家自然科学基金资助项目(10371112) |
| |
| 摘 要： | 有向网络上的最优有向连接问题是寻求从若干起点到若干终点的连接方式，使连接费用为最小。已知此问题是NP一困难问题。目前的一个研究方向是探讨存在多项式时间算法的特殊情形。本文研究了这样的特殊情形：树网络上所有起点处于同一条路上，建立了多项式时间算法。
|
| 关 键 词： | 网络优化 有向连接问题 树网络 多项式时间算法 |
| 文章编号： | 1004-3918(2004)04-0438-03 |
| 修稿时间： | 2004-03-05 |
An optimal directed connection problem in tree networks |
| |
| LIN Hao,WAN Jian-jun. An optimal directed connection problem in tree networks[J]. Henan Science, 2004, 22(4): 438-440 |
| |
| Authors: | LIN Hao WAN Jian-jun |
| |
| Abstract: | 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. |
| |
| Keywords: | network optimization directed connection problem treenetwork polynomial algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
