首页 | 本学科首页   官方微博 | 高级检索  
     检索      

导出匹配问题的NP-完全性以及导出匹配可扩问题的CO-NP-完全性
引用本文:原晋江,杨帆.导出匹配问题的NP-完全性以及导出匹配可扩问题的CO-NP-完全性[J].运筹学学报,2000,4(1):76-80.
作者姓名:原晋江  杨帆
作者单位:1. 郑州大学数学系,郑州,450052
2. 中国科学院系统科学研究所,北京,100080
基金项目:Research partially supported by the National Natural Science Foundation of China and the Excellent Young Foundation of Henan Province.
摘    要:图G的一个匹配M是导出的,若M是图G的一个导出子图。图G是导邮匹配可扩的(简记IM-可扩的),若图G的任一导出匹配均含于图G的一个完美匹配当中。本文我们将证明如下结果。⑴对无爪图而言,问题“给定图G以及一个正整数r,确定是否存在图G的一个导出匹配M使得M≥r”是NP-完全的。⑵对直径为2的图以及直径为3的偶图,问题“确定一个给定图是否为导出匹配可扩的”是CO-NP完全的;而对完全多部图而言,问题“

关 键 词:  CO-NP-完全性  导出匹配问题  导出匹配可扩
修稿时间:1998-05-26

NP-Completeness of Induced Matching Problem and Co-NP-Completeness of Induced Matching Extendable Problem
JINJIANG YUAN,FAN YANG.NP-Completeness of Induced Matching Problem and Co-NP-Completeness of Induced Matching Extendable Problem[J].OR Transactions,2000,4(1):76-80.
Authors:JINJIANG YUAN  FAN YANG
Institution:JINJIANG YUAN (Department of Mathematics, Zhengzhou University, Zhengzhou 450052, China))FAN YANG ((Institute of Systems Science, Academia Sinica, Beijing 100080, China))
Abstract:A matching M of a graph G is induced, if M is an induced subgraph of G. A graph G is induced matching extendable (simply IM-extendable), if every induced matching M of G is included in a perfect matching of G. In this paper we will prove the following results. (1) The problem "given a graph G and a positive integer r, determine whether there is an induced matching M of G such that |M| ≥ r" is NP-complete for claw-free graphs. (2) The problem "determine whether a given graph is IM-extendable" is co-NP-complete for graphs with diameter 2 and bipartite graphs with diameter 3 but linearly solvable for complete multi-partite graphs.
Keywords:Matching  IM-extendable  co-NP-completeanalysis  
本文献已被 CNKI 维普 万方数据 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号