树的最大基数匹配的并行算法

A PARALLEL ALGORITHM FOR FINDING THE MAXIMUM CARDINALITY MATCHING OF A TREE

本文在给出了起点集的概念并讨论其性质的基础上,得出了在CREW-PRAM机器模型上寻找根树最大基数匹配的并行算法,设根树T=(V,E)中,|V|=n,叶子数为m,高度为h,则用本算法在m个处理机上,寻找T的最大基数匹配的时间复杂度为O(t·h),其中t=min{log(n+1),[h/2]}.

Following an introduction and a brief discussion of the concept of 'starting vertices set', the paper gives a parallel algorithm for finding the maximum cardinality matching of a tree. For a tree T=(V, E) which has n vertices, m leaves and height of h, its maximum cardinality matching can bc found with time complexity O(t·h) using m processors in CREW-PRAM model, where t=min{log(n+1), [h/2]}.