- 相关推荐
小直径图的导出匹配覆盖
设G是一个图,而M1,M2,…,Mk是G的k个导出匹配.称{M1,M2,…,Mk}是图G的一个k-导出匹配覆盖,若V(M1)∪V(M2)∪…∪V(Mk)=V(G).k-导出匹配覆盖问题是指对任一个给定的图G是否存在一个k-导出匹配覆盖.这篇文章证明了:直径为6的图的2-导出匹配覆盖问题和直径为2的图的3-导出匹配覆盖问题是NP-完备的,直径为2的图的2-导出匹配覆盖问题多项式可解.
作 者： 董丽 原晋江 Dong Li Yuan Jinjiang 作者单位： 董丽,Dong Li(信阳师范学院数学与信息科学学院,信阳,464000)原晋江,Yuan Jinjiang(郑州大学数学系,郑州,450052)
刊 名： 运筹学学报 ISTIC PKU 英文刊名： OPERATIONS RESEARCH TRANSACTIONS 年，卷(期)： 2008 12(2) 分类号： O22 关键词： 运筹学 导出匹配 导出匹配覆盖 NP-完备 多项式可解 Operations research induced matching induced matching cover NP-complete polynomially solvable【小直径图的导出匹配覆盖】相关文章：
具最小度距离的完美匹配单圈图04-26
直径为3的3-正则简单平面图的完全刻画04-26
图像匹配在海底地图匹配中的应用04-26
大直径FZSi中的微缺陷研究04-27
区域覆盖混合星座设计04-27
图的倍图与补倍图04-26
升华法生长大直径的SiC单晶04-26
一类最小覆盖问题04-26
基站覆盖规划方案是否合理04-27
导出双粒子纠缠态表象的新途径04-26