关于图划分中的一个计算复杂性问题

• 作者: 杨晓霖 黄元秋
• 来源期刊: 湖南文理学院学报（自然科学版）
• 学科: 数学
• 关键词: 图 计算复杂性 NP-完全的 Xoung-树 仙人掌图
• 年，卷（期）: 2005,（1）
• 所属期刊栏目: 数学
• 页码范围: 7-11
• 页数: 5页
• 分类号: O157.5
• 字数: 1788字
• 语种: 中文
• DOI: 10.3969/j.issn.1672-6164.2005.01.004

摘要

一个稳定集是一个图的相互不相邻的顶点集,一个仙人掌图是一个任意两个圈都没有公共点的连通图.本文我们考虑如下问题,称之为STABLE CACTUS-问题的计算复杂性:给定一个图G,G中是否存在稳定集S使得G-S是一个仙人掌图.我们证明了STABLE CACTUS-问题是一个NP-完全问题,甚至可以进一步限制给定的图G是最大度不超过4的偶图.这个结果在图的度条件下是最好的了,我们利用图的最大亏格研究中的Xoung-树方法,证明了如果G是一个最大度不超过3的图,则STABLE CACTUS-问题是多项式时间可解的.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	黄元秋	湖南师范大学数学系	111	474	13.0	17.0
2	杨晓霖	南华大学数理学院	12	38	4.0	6.0