树状网络上带度约束的k-tree core问题

k-tree core problem with degree constraint in tree network

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

According to background of actual application,the processing ability of each equipment is limited generally in the computer and correspondence networks.The article puts forward the k-tree core problem with degree constraint in a tree network, denoted as q-DTC （k）（Degree constrained Tree Core）.With the method of dynamic programming,adopting optimizing principle,it finds out local rooted cores.Then making use of greedy idea,the branch of node which is dissatisfied with degree constraint must be deleted.It takes O（kn） and O（max{n log n,kn}） time algorithm for unweighted tree and weighted tree.