An Emcient Parallel Graph Edge Matching Algorithm and Its Applications

摘要

A fast and efficient parallel algorithm for finding a maximal edge matching in an undirected graph G(V E) is proposed. It runs in O(logn) time with O(m/ logn + n) processors on an EREW PRAM for a class of graph set II, where n = |v|, m = |E| and n includes at least (i) planar graphs; (ii) graphs of bounded genus; and (iii) graphs of bounded maximum degree and so on. Our algorithm improves the previously known best algorithms by a factor of logn in the time complexity with linear number of processors on EREW PRAMs when the input is limited to II.