AN EFFICIENT NC ALGORITHM FOR APPROXIMATE MAXIMUM WEIGHT MATCHING
Satyajit Banerjee · Discrete Mathematics Algorithms and Applications · 2013
We present an alternative implementation of the (1 – ϵ) factor NC approximation algorithm for the maximum weight matching by Hougardy et al. [1]. Our implementation, on the EREW PRAM model of computation, achieves an [Formula: see text] factor improvement on both the execution time and the number of processors.