期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息
共找到1篇文章
< 1 >
每页显示 20 50 100
已选择0条
导出题录 引用分析
参考文献
引证文献
 统计分析
检索结果
已选文献
显示方式：
关于图划分中的一个计算复杂性问题(英文)
1
作者 杨晓霖 黄元秋 《湖南文理学院学报（自然科学版）》 CAS 2005年第1期7-11,共5页
一个稳定集是一个图的相互不相邻的顶点集,一个仙人掌图是一个任意两个圈都没有公共点的连通图.本文我们考虑如下问题,称之为STABLECACTUS -问题的计算复杂性:给定一个图G ,G中是否存在稳定集S使得G -S是一个仙人掌图.我们证明了STABLEC... 一个稳定集是一个图的相互不相邻的顶点集,一个仙人掌图是一个任意两个圈都没有公共点的连通图.本文我们考虑如下问题,称之为STABLECACTUS -问题的计算复杂性:给定一个图G ,G中是否存在稳定集S使得G -S是一个仙人掌图.我们证明了STABLECACTUS -问题是一个NP-完全问题,甚至可以进一步限制给定的图G是最大度不超过4的偶图.这个结果在图的度条件下是最好的了,我们利用图的最大亏格研究中的Xoung -树方法,证明了如果G是一个最大度不超过3的图,则STABLECACTUS -问题是多项式时间可解的. 展开更多
关键词 复杂性问题 图划分 NP-完全问题 多项式时间可解 仙人掌图 计算复杂性 最大亏格 稳定集 最大度 顶点集 连通图 公共点 度条件 图G 证明 偶图
下载PDF
已选择0条
导出题录 引用分析
参考文献
引证文献
 统计分析
检索结果
已选文献
上一页 1 下一页 到第 页
使用帮助 返回顶部