树状网络上k-tree center问题

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