导出匹配问题的NP-完全性以及导出匹配可扩问题的CO-NP-完全性

• 作者: 原晋江 杨帆
• 来源期刊: 运筹学学报
• 学科: 数学
• 关键词: 匹配 IM-可扩 CO-NP-完全
• 年，卷（期）: 2000,（1）
• 页码范围: 76-80
• 页数: 5页
• 分类号: O22
• 语种: 中文
• DOI: 10.3969/j.issn.1007-6093.2000.01.008

摘要

图G的一个匹配M是导出的,若M是图G的一个导出子图. 图G是导出匹配可扩的(简记IM-可扩的),若图G的任一导出匹配均含于图G的一个完美匹配当中.本文我们将证明如下结果. (1)对无爪图而言,问题"给定图G以及一个正整数r,确定是否存在图G的一个导出匹配M使得|M|≥r"是NP-完全的. (2)对直径为2的图以及直径为3的偶图,问题"确定一个给定图是否为导出匹配可扩的"是CO-NP-完全的;而对完全多部图而言,该问题线性可解.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	杨帆	中国科学院系统科学研究所	180	1565	19.0	33.0
2	原晋江	郑州大学数学系	26	97	6.0	7.0