树状网络上多约束的tree core问题  

The Tree Core Problem with Some Constraint in a Tree Network

作　　者：杨建芳[1] 刘建贞[1] 

机构地区：[1]杭州市电子科技大学运筹与控制研究所,浙江杭州3100181

出　　处：《杭州电子科技大学学报（自然科学版）》2012年第2期63-65,共3页Journal of Hangzhou Dianzi University：Natural Sciences

基　　金：国家自然科学基金面上资助项目(11071219);国家自然科学天元基金资助项目(11026107);浙江省自然科学基金资助项目(Y6090080;Y1090465);浙江省教育厅基金资助项目(Y201016901)

摘　　要：考虑到在实际应用中,由于计算机和通信网络中一般每个设备的处理能力是有限的,以及控制各设备放置点之间的营运成本,该文在tree core问题的基础上,提出了同时带有度和半径约束的tree core问题,记为(q,l)-DTC问题(Degree constrained Tree Core)。该文先构造出极大子树集,然后在极大子树中利用动态规划的方法,求解(q,l)-DTC问题,可在O(n2)时间内求得该问题的最优解。According to background of actual application,because of the processing ability of each equipment is limited generally in the computer and correspondence networks,and the cost between each equipment is controlled.The paper puts forward the tree core problem with degree and radius constraint in a tree network,denoted as problem.The first is to structure-maximal subtree of,then the second is to use the method of dynamic programming to solve problem.It takes time algorithm for this problem.

关 键 词：树核问题 极大子树 动态规划 

分 类 号：TP393.01[自动化与计算机技术—计算机应用技术]