An Efficient Parallel Graph Edge Matching Algorithmand 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/log+n+n) processors on an EREW PRAM for a class of graph set Ⅱ, where n=V, m = E and Ⅱ includes at leut (i) planar graphs; (ii) graphs of bounded genus; and (iii) graphs of bounded maximum degree and so on. Our algorithm improves the previoualy known best algoritbms by a factor of logn in the time complexity…