AN IMPROVED MAXIMAL MATCHING ALGORITHM

作     者：S. B. YANG S. K. DHALL S. LAKSHMIVARAHAN 

作者机构：School of Electrical Engineering and Computer Science University of Oklahoma Norman Oklahoma 73019 U.S.A. 

出 版 物：《Parallel Processing Letters》 

年 卷 期：1991年第1卷第2期

页      面：135-142页

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Parallel randomized algorithm maximal matching 

摘      要：In this paper we present a randomized parallel maximal matching algorithm that requires only O(n) processors on an. EREW PRAM, where n is the number of vertices in an undirected graph G = (V, E). Our algorithm outputs a matching in O( log 2 m) expected time, where m is the number of edges in G. The probability that the output of our algorithm is maximal is at least 1 − e −k , where k is a constant.