固定顶点的树划分问题

Tree partition problems with some fixed vertices

  • 摘要: 考虑了2个固定顶点的树划分问题,即固定k个顶点的最小和树划分问题和固定k个顶点的最小最大树划分问题,我们得到如下结果:①利用Greedy技巧,得到固定k个顶点的最小和树划分问题的最优多项式算法;②证明了固定k个顶点的最小最大树划分问题是NP-难的,并利用①的结果给出了固定k个顶点的最小最大树划分问题的一个k-近似算法.

     

    Abstract: Two problems of tree partition with some fixed vertices were considered in this paper,i.e.min-sum tree partition with fixed k vertices and min-max tree partition with fixed k vertices,the following results were obtained,① there exists an optimal and polynomial algorithm to the first problem;② the second problem was proved to be NP-hard,and there exists a k-approximate algorithm to the second problem.

     

/

返回文章
返回