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