EFFICIENT IMPLEMENTATION OF EDMONDS ALGORITHM FOR MAXIMUM MATCHING ON GRAPHS
EFFICIENT IMPLEMENTATION OF EDMONDS ALGORITHM FOR MAXIMUM MATCHING ON GRAPHS
复制标题
DOI：
10.1145/321941.321942
复制
发表时间：
1976-01-01
影响因子：
2.5
通讯作者：
GABOW, HN
中科院分区：
文献类型：
--
作者：
GABOW, HN
图上的匹配是一组边，其中没有两个共享一个顶点。最大匹配包含尽可能多的边。本文提出了一种有效的实现埃德蒙兹的算法寻找一个最大的匹配。计算时间与V3成比例，其中V是顶点的数量; Edmonds算法的先前实现的计算时间与V4成比例。该实现是基于一个系统的标签，编码交替路径的结构。
A matching on a graph is a set of edges, no two of which share a vertex. A maximum matching contains the greatest number of edges possible. This paper presents an efficient implementation of Edmonds' algorithm for finding a maximum matching. The computation time is proportional toV3, whereVis the number of vertices; previous implementations of Edmonds' algorithm have computation time proportional toV4. The implementation is based on a system of labels that encodes the structure of alternating paths.