逼近4正则图的最小顶点覆盖问题的难解性

陈文彬

首页> 中文期刊> 《广州大学学报（自然科学版）》 >逼近4正则图的最小顶点覆盖问题的难解性

逼近4正则图的最小顶点覆盖问题的难解性

开具论文收录证明 >>

期刊封面封底目录下载 >>

文献代查 >>

页面导航

摘要
著录项
相似文献
相关主题

摘要

证明了逼近4正则图的最小顶点覆盖问题在某个常数因子内是计算难解的.相似地,对于5正则图、6正则图等的最小顶点覆盖问题,这个结论也成立.已知逼近3正则图的最小顶点覆盖问题在某个常数因子内是计算难解的,文章扩展了这个结果到4正则图情况,用K-归约证明这个结果,给出了一个从3正则图的最小顶点覆盖问题到4正则图的最小顶点覆盖问题的K-归约.

著录项

来源
《广州大学学报（自然科学版）》 |2014年第1期|65-69|共5页
作者
陈文彬;
展开▼
作者单位

广州大学计算机科学与教育软件学院,广东广州510006;

展开▼
原文格式 PDF
正文语种 chi
中图分类计算复杂性理论;
关键词
NP-难解性; 计算复杂性; 正则图; 顶点覆盖; 近似性;

相似文献

中文文献
外文文献
专利

1. 逼近MAX 3SAT-2问题的难解性（英文） [J] . 陈文彬 . 广州大学学报（自然科学版） . 2012,第002期
2. 计算问题的空间难解性 [J] . 刘传领 ,宋玉杰 ,连祥凯 . 商丘职业技术学院学报 . 2003,第003期
3. 基于团问题难解性的密钥分级管理协议 [J] . 赵一鸣 ,鲍振东 . 电子学报 . 2000,第011期
4. 一类具有Lipschitz条件的非线性变分包含问题解的存在性和Ishikawa迭代逼近问题 [J] . 谷峰 . 西南师范大学学报（自然科学版） . 2006,第004期
5. 一类非线性变分包含问题解的存在性和Mann迭代逼近问题 [J] . 李晓红 . 黑龙江大学自然科学学报 . 2005,第001期
6. 团问题难解性及在密密钥分级管理中的应用 [C] . 赵一鸣 ,鲍振东 . 中国计算机学会信息保密专业委员会年会 . 1999
7. 最小顶点覆盖问题的几种DNA算法研究 [A] . 郭洪敏 . 2016

逼近4正则图的最小顶点覆盖问题的难解性

摘要

著录项

相似文献

相关主题

期刊订阅