Finding the Maximum Matching in a Bipartite Graph
Finding the Maximum Matching in a Bipartite Graph
复制标题
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
B. Alom;Someresh Das;Md. Saiful Islam
中科院分区：
文献类型：
--
作者：
B. Alom;Someresh Das;Md. Saiful Islam
图G的匹配M是一个边集，使得M的两条边没有共享端点。对于二部图G = (V， E)，最大匹配是指在所有匹配中基数最大的匹配。现有的最大匹配枚举算法每次匹配的时间复杂度为0 （|V |）。FordFulkerson方法在O（VE）时间内找到二部图上的最大匹配。本文提出了一种在O(E)时间内求二部图上最大匹配的算法，该算法比现有算法的时间复杂度要小。
A matching M of the graph G is an edge set such that no two edges of M share their endpoints. For a bipartite graph G = (V, E) maximum matching are matching whose cardinalities are maximum among all matchings. Existing enumerating algorithm of maximum matching has time complexity is O(|V |) per matching. FordFulkerson method finds the maximum matching on a bipartite graph with O(VE) time. In this paper, an algorithm to find the maximum matching on a bipartite graph with O(E) time is presented which is less than the time complexity of the existing algorithms.