摘要
二部图作为一种非常重要的数据结构有很多特殊性质,针对文献[4]中的二部图的所有极大匹配求解算法,给出了反例证明了该算法是错误的,同时证明了二部图的所有极大匹配的求解是NP难问题。
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.
出处
《电脑开发与应用》
2011年第8期11-12,共2页
Computer Development & Applications
关键词
二部图
匹配
极大匹配
算法
NP难
bipartite graph
matching
maximal matching
algorithm
NP-hard
