| 二部图的所有极大匹配 |
| |
| 引用本文： | 王文虎,杨雨. 二部图的所有极大匹配[J]. 电脑开发与应用, 2011, 24(8): 11-12 |
| |
| 作者姓名： | 王文虎 杨雨 |
| |
| 作者单位： | 1. 平顶山学院软件学院 河南平顶山 467000
2. 平顶山学院国际教育交流学院 河南平顶山 467000 |
| |
| 摘 要： | 二部图作为一种非常重要的数据结构有很多特殊性质,针对文献[4]中的二部图的所有极大匹配求解算法,给出了反例证明了该算法是错误的,同时证明了二部图的所有极大匹配的求解是NP难问题.
|
| 关 键 词： | 二部图 匹配 极大匹配 算法 NP难 |
All Maximal Matching of Bipartite Graph |
| |
| Wang Wenhu et al. All Maximal Matching of Bipartite Graph[J]. Computer Development & Applications, 2011, 24(8): 11-12 |
| |
| Authors: | Wang Wenhu et al |
| |
| Affiliation: | Wang Wenhu et al |
| |
| Abstract: | As a very important data structure,bipartite graph has many special properties,a counter example which prove the algorithm(all maximal bipartite graph matching algorithm) in paper[4] is wrong was given out,and we also prove that the enumeration of maximal bipartite graph matching in bipartite graph is NP-hard. |
| |
| Keywords: | bipartite graph matching maximal matching algorithm NP-hard |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
