摘要
建立了二部图G=(V,U,E)的二级优先匹配规则,在此规则下,用改进的深度优先搜索对匹配算法进行改进,使得算法能够根据连通分量的个数动态优化算法的性能,使动态最大匹配算法的时间复杂度提高到O(max(|V|,|E|,m|U|)).
Establishing a matching rule in order of precedence of two level in Bipartite Graphs, Under the rule, making use of improved Depth-First Search to mend the matching algorithm,thus the mended algorithm is able to adjust performance of self according to the number of connected component in Bipartite Graphs, whose time complexity is O（max（ ｜V｜, ｜E｜ ,m｜U｜）.
出处
《鲁东大学学报（自然科学版）》
2006年第3期168-170,177,共4页
Journal of Ludong University:Natural Science Edition
基金
鲁东大学校科研基金资助项目(202-19160301)
关键词
二部图
最大匹配
二级优先
动态深度优先搜索
bipartite graphs
maximum matching
precedence of two level
dynamic DFS
