摘要
众所周知,从通讯网络建设中提出著名的最优支撑树问题,即在一个赋权连通图中求一个包含所有顶点而权(费用)最小的连通子图(支撑树).进而,在交通、通讯、供销系统的干线设计中,考虑的连线(干线)不一定连接网络的所有顶点,但被连接的顶点必须构成一个控制集,即其余任一顶点都有一条边直接与此主干部分相连.这就提出了最优控制树问题.似乎此问题与最优支撑树问题十分类似,但我们将证明它是NP-困难的,并给出一个分枝定界算法及相关性质.
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 neeessarily 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 axe as follows： the NP-hardness of the problem, a branch-and-bound algorithm and related properties.
出处
《系统工程理论与实践》
EI
CSCD
北大核心
2006年第5期83-87,共5页
Systems Engineering-Theory & Practice
基金
国家自然科学基金(10371112)
河南工业大学校科研基金(0402008)
关键词
网络优化
支撑树
控制树
计算复杂性
分枝定界算法
network optimization
spanning tree
dominating tree
computational complexity
branch-and-bound algorithm
