Approximating Matchings in Parallel,

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 1991
Accession Number
ADA323450

Entities

People

  • A. V. Goldberg
  • S. Plotkin
  • T. Fischer

Organizations

  • Stanford University

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Commerce
  • Computations
  • Computer Programs
  • Computer Science
  • Computers
  • Construction
  • Customer Services
  • Government (Foreign)
  • Governments
  • Iterations
  • Operations Research
  • Parallel Computing
  • Sequences
  • Trees (Data Structures)
  • Universities

Fields of Study

  • Computer science

Readers

  • Graph Algorithms and Convex Optimization.