| 小直径图的导出匹配覆盖 |
| |
| 引用本文： | 董丽,原晋江.小直径图的导出匹配覆盖[J].运筹学学报,2008,12(2):17-24. |
| |
| 作者姓名： | 董丽 原晋江 |
| |
| 作者单位： | 1. 信阳师范学院数学与信息科学学院,信阳,464000
2. 郑州大学数学系,郑州,450052 |
| |
| 摘 要： | 设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-导出匹配覆盖问题多项式可解.
|
| 关 键 词： | 运筹学 导出匹配 导出匹配覆盖 NP-完备 多项式可解 Operations research induced matching induced matching cover NP-complete polynomially solvable 小直径 导出匹配 覆盖问题 Induced Diameter Small Graph solvable paper graphs diameter problem cover induced 多项式可解 存在 |
Cover a Graph with Small Diameter by Induced Matchings |
| |
| Dong Li,Yuan Jinjiang.Cover a Graph with Small Diameter by Induced Matchings[J].OR Transactions,2008,12(2):17-24. |
| |
| Authors: | Dong Li Yuan Jinjiang |
| |
| Abstract: | Let G be a graph and M1, M2,…, Mk are k induced matchings of G. We say{M1,M2,…,Mk}is a k-induced-matching cover of G if V(M1)∪V(M2)∪…∪ V(Mk)=V(G). The k-induced-matching cover problem asks whether a given graph G has a k-induced-matching cover or not. This paper shows that 2-induced-matching cover problem of graphs with diameter 6 and 3-induced-matching cover problem of graphs with diameter 2 are NP-complete, and 2-induced-matching cover problem of graphs with diameter 2 is polynomially solvable. |
| |
| Keywords: | Operations research induced matching induced matching cover NP-complete polynomially solvable |
| 本文献已被 维普 万方数据 等数据库收录！ |
|
