小直径图的导出匹配覆盖
设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