Report Number: CS-TR-91-1369
Institution: Stanford University, Department of Computer Science
Title: Approximating matchings in parallel
Author: Fischer, Ted
Author: Goldberg, Andrew V.
Author: Plotkin, Serge
Date: June 1991
Abstract: We show that for any constant k > O, a matching with cardinality at least 1 - 1/(k+1) times the maximum can be computed in NC.
http://i.stanford.edu/pub/cstr/reports/cs/tr/91/1369/CS-TR-91-1369.pdf