排序方式: 共有1条查询结果,搜索用时 15 毫秒
1
1.
导出匹配问题的NP-完全性以及导出匹配可扩问题的CO-NP-完全性 总被引:8,自引:0,他引:8
图G的一个匹配M是导出的,若M是图G的一个导出子图。图G是导邮匹配可扩的(简记IM-可扩的),若图G的任一导出匹配均含于图G的一个完美匹配当中。本文我们将证明如下结果。⑴对无爪图而言,问题“给定图G以及一个正整数r,确定是否存在图G的一个导出匹配M使得M≥r”是NP-完全的。⑵对直径为2的图以及直径为3的偶图,问题“确定一个给定图是否为导出匹配可扩的”是CO-NP完全的;而对完全多部图而言,问题“ 相似文献
1