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

摘要：

考虑到在实际应用中,由于计算机和通信网络中一般每个设备的处理能力是有限的,以及控制各设备放置点之间的营运成本,该文在tree core问题的基础上,提出了同时带有度和半径约束的tree core问题,记为(q,1)-DTC问题(Degree constrained Tree Core).该文先构造出极大子树集,然后在极大子树中利用动态规划的方法,求解(q,1) - DTC问题,可在O(n2)时间内求得该问题的最优解.

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

所属期刊栏目：32

分类号：TP393.01(计算技术、计算机技术)

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

在线出版日期：2012-10-25（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：63-65