| 点赋权图上固定顶点的树划分问题 |
| |
| 引用本文： | 张同全.点赋权图上固定顶点的树划分问题[J].云南民族大学学报(自然科学版),2007,16(4):303-305. |
| |
| 作者姓名： | 张同全 |
| |
| 作者单位： | 云南民族大学,数学与计算机科学学院,云南昆明650091;云南大学,物理科学技术学院非线性中心,云南昆明650091 |
| |
| 基金项目： | 云南省教育厅科学研究基金资助项目 |
| |
| 摘 要： | 考虑了点赋权图上固定k个顶点的树划分问题.首先证明了点赋树图上固定k个顶点的最小最大树划分问题是NP-难的,然后给出了该问题的一个启发式算法,最后证明了该算法是点赋权完全图上固定k个顶点的最小最大树划分问题的一个2-1k近似算法.
|
| 关 键 词： | 反圈 启发式算法 导出子图 近似算法 |
| 文章编号： | 1672-8513（2007）04-0303-03 |
| 收稿时间： | 2007-03-26 |
| 修稿时间： | 2007年3月26日 |
Tree Partition Problem of the Fixed Vertices on the Vertex-Weighted Graphs |
| |
| Zhang Tongquan.Tree Partition Problem of the Fixed Vertices on the Vertex-Weighted Graphs[J].Journal of Yunnan Nationalities University:Natural Sciences Edition,2007,16(4):303-305. |
| |
| Authors: | Zhang Tongquan |
| |
| Institution: | 1. Department of Mathematics and Computer Science, Yunnan Nationalities University, Kunming 650031, China; 2. Nonlinear Complex System Center, College of Physics Science and Technologies, Yunnan University, Kunming 650091, China |
| |
| Abstract: | This paper discusses the Min-max tree partition problem of the fixed vertices on the vertex-weighted 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-1k for the problem on the completed graphs. |
| |
| Keywords: | anti-cycle heuristic algorithm induced subgraph approximate algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
