| 关于图划分中的一个计算复杂性问题 |
| |
| 引用本文： | 杨晓霖,黄元秋.关于图划分中的一个计算复杂性问题[J].湖南文理学院学报(自然科学版),2005,17(1):7-11. |
| |
| 作者姓名： | 杨晓霖 黄元秋 |
| |
| 作者单位： | 南华大学数理学院,湖南,衡阳,421001;湖南师范大学,数学系,湖南,长沙,410081 |
| |
| 基金项目： | 国家自然科学基金
,
湖南省教育规划项目 |
| |
| 摘 要： | 一个稳定集是一个图的相互不相邻的顶点集,一个仙人掌图是一个任意两个圈都没有公共点的连通图.本文我们考虑如下问题,称之为STABLE CACTUS-问题的计算复杂性:给定一个图G,G中是否存在稳定集S使得G-S是一个仙人掌图.我们证明了STABLE CACTUS-问题是一个NP-完全问题,甚至可以进一步限制给定的图G是最大度不超过4的偶图.这个结果在图的度条件下是最好的了,我们利用图的最大亏格研究中的Xoung-树方法,证明了如果G是一个最大度不超过3的图,则STABLE CACTUS-问题是多项式时间可解的.
|
| 关 键 词： | 图 计算复杂性 NP-完全的 Xoung-树 仙人掌图 |
A Problem on the Computational Complexity of Graph Partitions |
| |
| YANG Xiao-lin,HUANG Yuan-qiu.A Problem on the Computational Complexity of Graph Partitions[J].Journal of Hunan University of Arts and Science:Natural Science Edition,2005,17(1):7-11. |
| |
| Authors: | YANG Xiao-lin HUANG Yuan-qiu |
| |
| Abstract: | A stable set of a graph was a subset of pairwise non-adjacent vertices. A cactus was a connected graph whose any two circuits are vertex-disjoint. The computational complexity of the following problem, called STABLE CACTUS problem was discassed: Given a graph G , whether G had a stable set S such that G-S was a cactus? That the STABLE CACTUS problem was NP-complete even for a bipartite graph with maximum degree 4 was proved.The result was best possible in terms of the degree condition, for applying Xoung-tree method used in the study of maximum genus of graphs,also the STABLE CACTUS problem was solvable in polynomial-time for any graph with maximum degree |
| |
| Keywords: | Graph stable set Computational complexity NP-complete Xoung-tree Cactus graph |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
