网络中的最优控制树问题

作     者：林浩 林澜 LIN Hao;LIN Lan

作者机构：河南工业大学理学院河南郑州450052 同济大学计算机科学与工程系上海200092 

基　　金：国家自然科学基金(10371112) 河南工业大学校科研基金(0402008) 

出 版 物：《系统工程理论与实践》 (Systems Engineering-Theory & Practice)

年 卷 期：2006年第26卷第5期

页      码：83-87页

摘      要：众所周知,从通讯网络建设中提出著名的最优支撑树问题,即在一个赋权连通图中求一个包含所有顶点而权(费用)最小的连通子图(支撑树).进而,在交通、通讯、供销系统的干线设计中,考虑的连线(干线)不一定连接网络的所有顶点,但被连接的顶点必须构成一个控制集,即其余任一顶点都有一条边直接与此主干部分相连.这就提出了最优控制树问题.似乎此问题与最优支撑树问题十分类似,但我们将证明它是NP-困难的,并给出一个分枝定界算法及相关性质.

主 题 词：网络优化 支撑树 控制树 计算复杂性 分枝定界算法 

学科分类：12[管理学] 1201[管理学-管理科学与工程类] 07[理学] 070105[070105] 0701[理学-数学类] 

核心收录：

D　O　I：10.3321/j.issn:1000-6788.2006.05.011

馆 藏 号：203511720...