Constructing a Perfect Matching is in Random NC,
Abstract
This document shows that the problem of constructing a perfect matching in a graph is in the complexity class Random NC; i.e., the problem is solvable in polylog time by a randomized parallel algorithm using a polynomial-bounded number of processors. It is also shown that several related problems lie in Random NC. These include: Constructing a perfect matching of maximum weight in a graph whose edge weights are given in unary notation; Constructing a maximum-cardinality matching; Constructing a matching covering a set of vertices of maximum weight in a graph whose vertex weights are given in binary; and Constructing a maximum s-t flow in a directed graph whose edge weights are given in unary. Additional keywords: rank functions. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 01, 1985
- Accession Number
- ADA157813
Entities
People
- A. Wigderson
- E. Upfal
- R. M. Karp
Organizations
- Stanford University