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.