张同全, 王泽磊, 李建平. 固定顶点的树划分问题[J]. 云南大学学报(自然科学版), 2005, 27(1): 1-4.
引用本文: 张同全, 王泽磊, 李建平. 固定顶点的树划分问题[J]. 云南大学学报(自然科学版), 2005, 27(1): 1-4.
ZHANG Tong-quan, WANG Ze-lei, LI Jian-ping. Tree partition problems with some fixed vertices[J]. Journal of Yunnan University: Natural Sciences Edition, 2005, 27(1): 1-4.
Citation: ZHANG Tong-quan, WANG Ze-lei, LI Jian-ping. Tree partition problems with some fixed vertices[J]. Journal of Yunnan University: Natural Sciences Edition, 2005, 27(1): 1-4.

固定顶点的树划分问题

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.

     

/

返回文章
返回