An efficient parallel graph edge matching algorithm and its applications

A fast and efficient parallel algorithm for finding a maximal edge matching in an undirected graphG(V,E) is proposed. It runs inO(logn) time with (M/logn+n) processors on an EREW PRAM for a class of graph set II, wheren=|V|, m=|E| and II 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. This research was supported in part by the National “863” Hi-Tech Program of China, the NSF of China, the NSF of Shandong Province, the Foundation of the Fellowship for the 21st Century of Shandong University and the Foundation of JSPS of Japan. Some content of the paper was presented at the IASTED International Conference on Parallel and Distributed Computing and Systems, Oct. 1996, Chicago, Illinois, USA. MA Jun received his B.S. degree from Shandong University of China in 1982, M.S. degree from Ibaraki University of Japan in 1988, and Ph.D. degree from Kyushu University of Japan in 1997, all in computer science. Now he is a Professor at the Computer Science Department of Shandong University. His research interests include design and analysis of algorithms, parallel and distributed processing, and AI. MA Shaohan graduated from the Department of Math of Shandong University of China in 1962. He was a research fellow at the Illinois University from 1985 to 1986. Now he is a Professor and the Dean of the Computer Science Department of Shandong University. His research interests include design and analysis of algorithms, parallel and distributed algorithms, and AI.