A parallel approximation algorithm for the weighted maximum matching problem

Abstract. ± We consider the problem of computing a matching in a large weighted graph using a parallel algorithm. Since an exact algorithm for the weighted matching problem is fairly costly we instead develop a fast approximation algorithm. The parallel algorithm is based on a distributed algorithm due to Hoepman [6]. Through experiments using both complete as well as sparse graphs we show that our new algorithm scales well using up to 32processors. 1