树状网络上k-tree center问题

The-tree Center Problem in a Tree Network

树状网络上的k-tree center问题是指在树上选择一棵叶子数恰好为k的子树,使得树上其他节点到该子树的最大距离最小化。由于center问题的目标函数是满足最大距离最小化,如果S是问题的最优解,则S肯定包含树的中心,因此在求解k-tree center问题时,首先找到树的中心,然后从中心出发,利用树收缩的思想逐步找到满足要求的子树。该文基于此对该问题给出了时间复杂度为O(kn)的多项式时间算法。

The k-tree center of a tree network is a subtree with exactly-leaves that minimizes the maximum distance from other vertexes to the subtree.Because the objective function of the k-tree center problem is minimax,so if S is the optimal solution,certainly S contains the center of the tree.Then in solving the k-tree center problem,the first is to find the center of the tree,then the second is to start from the center using the method of tree contraction to gradually get the satisfied subtree.In this paper,accor...