论文部分内容阅读
考虑到在实际应用中，由于计算机和通信网络中一般每个设备的处理能力是有限的，在k-tree core问题的基础上，提出了同时带有度约束的k-tree core问题，即k-tree core中的每个节点在子树中的度不超过给定常数q，记为q—DTC（k）（Degree constrained Tree Core）。利用动态规划的方法，采用最优化原则先找出文中所定义的局部根核集，然后利用贪婪思想对不满足度限制的节点所在的分支加以删减，对无权树和赋权树得到了复杂度分别为O（kn）和O（max{n logn，kn}）