固定顶点的树划分问题  

Tree partition problems with some fixed vertices

作　　者：张同全[1] 王泽磊[1] 李建平[1] 

机构地区：[1]云南大学数学系,云南昆明650091

出　　处：《云南大学学报（自然科学版）》2005年第1期1-4,共4页Journal of Yunnan University(Natural Sciences Edition)

基　　金：国家自然科学研究基金资助项目(10271103);云南省自然科学研究基金资助项目(2003F0015M).

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

关 键 词：顶点 多项式算法 近似算法 证明 NP 最优 固定 问题 技巧 利用 

分 类 号：N945.14[自然科学总论—系统科学] O157.5[理学—数学]