摘要
考虑了点赋权图上固定k个顶点的树划分问题.首先证明了点赋树图上固定k个顶点的最小最大树划分问题是NP-难的,然后给出了该问题的一个启发式算法,最后证明了该算法是点赋权完全图上固定k个顶点的最小最大树划分问题的一个2-1k近似算法.
This paper discusses the Min - max tree partition problem of the fixed vertices on the vertexweighted graphs. The NP - hardness of this problem is proved. A heuristic algorithm is presented, and it is proved to be an approximate algorithm of factor 2 -1/k for the problem on the completed graphs.
出处
《云南民族大学学报（自然科学版）》
CAS
2007年第4期303-305,共3页
Journal of Yunnan Minzu University:Natural Sciences Edition
基金
云南省教育厅科学研究基金资助项目
关键词
反圈
启发式算法
导出子图
近似算法
anti-cycle
heuristic algorithm
induced subgraph
approximate algorithm.
