-
题名树状网络上带度约束的k-tree core问题
被引量：1
- 1
-
-
作者
杨建芳
刘建贞
黄孙琴
-
机构
杭州电子科技大学理学院运筹与控制研究所
浙江长征职业技术学院基础部
-
出处
《计算机工程与应用》
CSCD
北大核心
2009年第34期41-43,共3页
-
基金
浙江省自然科学基金No.y606026
杭州电子科技大学科学研究基金No.KYF091507018~~
-
文摘
考虑到在实际应用中,由于计算机和通信网络中一般每个设备的处理能力是有限的,在k-treecore问题的基础上,提出了同时带有度约束的k-treecore问题,即k-treecore中的每个节点在子树中的度不超过给定常数q,记为q-DTC(k)(Degree constrained TreeCore)。利用动态规划的方法,采用最优化原则先找出文中所定义的局部根核集,然后利用贪婪思想对不满足度限制的节点所在的分支加以删减,对无权树和赋权树得到了复杂度分别为O(kn)和O(max{nlogn,kn})多项式时间算法,其中n是树的节点数。
-
关键词
tree
core问题
动态规划
局部根核
贪婪思想
-
Keywords
tree core problem
dynamic programming
local rooted core
greed idea
-
分类号
O157.5
[理学—基础数学]
-
-
题名树状网络上多约束的tree core问题
- 2
-
-
作者
杨建芳
刘建贞
-
机构
杭州市电子科技大学运筹与控制研究所
-
出处
《杭州电子科技大学学报（自然科学版）》
2012年第2期63-65,共3页
-
基金
国家自然科学基金面上资助项目(11071219)
国家自然科学天元基金资助项目(11026107)
+2 种基金
浙江省自然科学基金资助项目(Y6090080
Y1090465)
浙江省教育厅基金资助项目(Y201016901)
-
文摘
考虑到在实际应用中,由于计算机和通信网络中一般每个设备的处理能力是有限的,以及控制各设备放置点之间的营运成本,该文在tree core问题的基础上,提出了同时带有度和半径约束的tree core问题,记为(q,l)-DTC问题(Degree constrained Tree Core)。该文先构造出极大子树集,然后在极大子树中利用动态规划的方法,求解(q,l)-DTC问题,可在O(n2)时间内求得该问题的最优解。
-
关键词
树核问题
极大子树
动态规划
-
Keywords
tree core problem
maximal subtree
dynamic programming
-
分类号
TP393.01
[自动化与计算机技术—计算机应用技术]
-
