| 网络中的最优控制树问题 |
| |
| 引用本文： | 林浩,林澜.网络中的最优控制树问题[J].系统工程理论与实践,2006,26(5):83-87. |
| |
| 作者姓名： | 林浩 林澜 |
| |
| 作者单位： | 1. 河南工业大学理学院,河南,郑州,450052
2. 同济大学计算机科学与工程系,上海,200092 |
| |
| 摘 要： | 众所周知,从通讯网络建设中提出著名的最优支撑树问题,即在一个赋权连通图中求一个包含所有顶点而权(费用)最小的连通子图(支撑树).进而,在交通、通讯、供销系统的干线设计中,考虑的连线(干线)不一定连接网络的所有顶点,但被连接的顶点必须构成一个控制集,即其余任一顶点都有一条边直接与此主干部分相连.这就提出了最优控制树问题.似乎此问题与最优支撑树问题十分类似,但我们将证明它是NP-困难的,并给出一个分枝定界算法及相关性质.
|
| 关 键 词： | 网络优化 支撑树 控制树 计算复杂性 分枝定界算法 |
| 文章编号： | 1000-6788(2006)05-0083-05 |
| 修稿时间： | 2004年8月10日 |
Optimal Dominating Trees in a Network |
| |
| LIN Hao,LIN Lan.Optimal Dominating Trees in a Network[J].Systems Engineering —Theory & Practice,2006,26(5):83-87. |
| |
| Authors: | LIN Hao LIN Lan |
| |
| Abstract: | It is well-known that the minimum weight spanning tree problem has arisen from the communication network construction.The problem is to find a spanning tree in a weighted graph with the minimum weight.In this paper we study a variant problem in which the required tree is not necessarily spanning but its vertex set forms a dominating set of the graph.This new problem comes from the main lines design in the transportation,communication and supply-demand systems.Our main results are as follows: the NP-hardness of the problem,a branch-and-bound algorithm and related properties. |
| |
| Keywords: | network optimization spanning tree dominating tree computational complexity branch-and-bound algorithm |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《系统工程理论与实践》浏览原始摘要信息 |
| 点击此处可从《系统工程理论与实践》下载免费的PDF全文 |
