Accession Number : ADA323450
Title : Approximating Matchings in Parallel,
Corporate Author : STANFORD UNIV CA DEPT OF COMPUTER SCIENCE
Personal Author(s) : Fischer, T. ; Goldberg, A. V. ; Plotkin, S.
PDF Url : ADA323450
Report Date : JUN 1991
Pagination or Media Count : 12
Abstract : We show that for any constant k > 0, a matching with cardinality at least 1 - 1/(k+1) times the maximum can be computed in NC. Matching is a fundamental combinatorial problem. Furthermore, the special case of bipartite matching seems to be a important problem of parallel computation. For example, an NC algorithm for bipartite matching would imply NC algorithms for the problems of constructing depth-first search trees in both directed and undirected graphs.
Descriptors : *PARALLEL PROCESSING, *COMBINATORIAL ANALYSIS, *MATCHING, ALGORITHMS, OPTIMIZATION, COMPUTATIONS, GRAPHS, ITERATIONS.
Subject Categories : Statistics and Probability
Computer Programming and Software
Distribution Statement : APPROVED FOR PUBLIC RELEASE