| 具有完美匹配的图的顶点覆盖问题 |
| |
| 引用本文： | 金珍,万龙.具有完美匹配的图的顶点覆盖问题[J].浙江大学学报(理学版),2013,40(5):506-508. |
| |
| 作者姓名： | 金珍 万龙 |
| |
| 作者单位： | 1. 南昌工程学院理学系,江西南昌,330099
2. 江西财经大学信息管理学院,江西南昌,330013 |
| |
| 摘 要： | 对具有完美匹配的无向图的顶点覆盖问题进行了研究，提出了2个相关的问题，并对它们的难解性做出了判断.
|
| 关 键 词： | 完美匹配 顶点覆盖 P问题 NP完全问题 |
| 收稿时间： | 2012-06-08 |
Vertex cover on graph with perfect matching |
| |
| JIN Zhen
,
WAN Long.Vertex cover on graph with perfect matching[J].Journal of Zhejiang University(Sciences Edition),2013,40(5):506-508. |
| |
| Authors: | JIN Zhen WAN Long |
| |
| Institution: | 1. Department of Science, Nanchang Institute of Technology, Nanchang 330099, Chi ha; 2. School of Information Technology, Jiangxi University of Finance and Economics, Nanchang 330013, China) |
| |
| Abstract: | We consider two related problems about vertex cover on graphs with perfect matching. We show that one problem belongs to P and the other is NP-complete. |
| |
| Keywords: | perfect matching vertex cover P-problem NP-complete problem |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《浙江大学学报(理学版)》浏览原始摘要信息 |
| 点击此处可从《浙江大学学报(理学版)》下载免费的PDF全文 |
