| 逼近4正则图的最小顶点覆盖问题的难解性(英文) |
| |
| 引用本文： | 陈文彬.逼近4正则图的最小顶点覆盖问题的难解性(英文)[J].广州大学学报(自然科学版),2014(1). |
| |
| 作者姓名： | 陈文彬 |
| |
| 作者单位： | 广州大学计算机科学与教育软件学院; |
| |
| 基金项目： | Our research has been supported by the National Science Foundation of China(NSFC)under GrantNo.11271097;the research project of Guangzhou Education Bureau under Grant No.2012A074;the project IIPL-2011-001 from Shanghai Key Laboratory of Intelligent Information Processing;the project KFKT2012B01 from State Key Laboratory for Novel Software Technology,Nanjing University |
| |
| 摘 要： | 证明了逼近4正则图的最小顶点覆盖问题在某个常数因子内是计算难解的.相似地,对于5正则图、6正则图等的最小顶点覆盖问题,这个结论也成立.已知逼近3正则图的最小顶点覆盖问题在某个常数因子内是计算难解的,文章扩展了这个结果到4正则图情况,用K-归约证明这个结果,给出了一个从3正则图的最小顶点覆盖问题到4正则图的最小顶点覆盖问题的K-归约.
|
| 关 键 词： | NP-难解性 计算复杂性 正则图 顶点覆盖 近似性 |
| 本文献已被 CNKI 等数据库收录！ |
|
