期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息
共找到1篇文章
< 1 >
每页显示 20 50 100
已选择0条
导出题录 引用分析
参考文献
引证文献
 统计分析
检索结果
已选文献
显示方式：
导出匹配问题的NP-完全性以及导出匹配可扩问题的CO-NP-完全性(英文) 被引量：9
1
作者 原晋江 杨帆 《运筹学学报》 CSCD 2000年第1期76-80,共5页
图Ｇ的一个匹配Ｍ是导出的，若Ｍ是图Ｇ的一个导出子图．图Ｇ是导出匹配可扩的（简记ＩＭ－可扩的），若图 Ｇ的任一导出匹配均含于图 Ｇ的一个完美匹配当中．本文我们将证明如下结果． （１）对无爪图而言，问题“给定图Ｇ以及一个正... 图Ｇ的一个匹配Ｍ是导出的，若Ｍ是图Ｇ的一个导出子图．图Ｇ是导出匹配可扩的（简记ＩＭ－可扩的），若图 Ｇ的任一导出匹配均含于图 Ｇ的一个完美匹配当中．本文我们将证明如下结果． （１）对无爪图而言，问题“给定图Ｇ以及一个正整数ｒ，确定是否存在图Ｇ的一个导出匹配Ｍ使得｜Ｍ｜≥ｒ”是ＮＰ－完全的． （２）对直径为２的图以及直径为３的偶图，问题“确定一个给定图是否为导出匹配可扩的”是ＣＯ－ＮＰ－完全的；而对完全多部图而言，该问题线性可解。 展开更多
关键词 图 CO-NP-完全性 导出匹配问题 导出匹配可扩
下载PDF
已选择0条
导出题录 引用分析
参考文献
引证文献
 统计分析
检索结果
已选文献
上一页 1 下一页 到第 页
使用帮助 返回顶部