论文部分内容阅读
A fast and efficient parallel algorithm for finding a maximal edge matching in an undirected graph G(V,E) is proposed. It runs inO (log n) time with O (m/log n+n) processors on an EREW PRAM for aclass of graph set Π, where n=|V|,m=|E| and Π includesat least (i) planar graphs;(ii) graphs of bounded genus; and (iii)graphs of bounded maximum degree and so on. Our algorithm improves thepreviously known best algorithms by a factor of logn in the timecomplexity with linear number of processors on EREW PRAMs when the inputis limited to Π.