导出匹配问题的np完全性以及导出匹配可扩问题的conp完全性英文

CSpace

	导出匹配问题的np完全性以及导出匹配可扩问题的conp完全性英文
	原晋江 1; 杨帆 2
	2000
发表期刊	运筹学学报
ISSN	1007-6093
卷号	4 期号:1 页码:76
摘要	图G的一个匹配M是导出的,若M是图G的一个导出子图.图G是导出匹配可扩的,若图G的任一导出匹配均含于图G的一个完美匹配当中.该文证明如下结果:(1)对无爪图而言,问题“给定图G以及一个正整数r,确定是否存在图G的一个导出匹配M使得\|M\|≥r”是NP-完全的.(2)对直径为2的图以及直径为3的偶图,问题“确定一个给定图是否为导出匹配可扩的”是CO-NP-完全的;而对完全多部图而言,该问题线性可解.
语种	英语
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/41224
专题	中国科学院数学与系统科学研究院
作者单位	1.郑州大学 2.中国科学院数学与系统科学研究院
推荐引用方式 GB/T 7714	原晋江,杨帆. 导出匹配问题的np完全性以及导出匹配可扩问题的conp完全性英文[J]. 运筹学学报,2000,4(1):76.
APA	原晋江,&杨帆.(2000).导出匹配问题的np完全性以及导出匹配可扩问题的conp完全性英文.运筹学学报,4(1),76.
MLA	原晋江,et al."导出匹配问题的np完全性以及导出匹配可扩问题的conp完全性英文".运筹学学报 4.1(2000):76.