Constructing a perfect matching is in random NC
type: Item
instance of: scholarly article
title: Constructing a perfect matching is in random NC
zbMATH Open document ID: 0646.05051
DOI: 10.1007/BF02579407
author: Richard Karp
author: Eli Upfal
author: A. Wigderson
published in: Combinatorica
publication date: 1986-01-01T00:00:00Z
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 4053671
zbMATH Keywords: constructing a perfect matching
zbMATH Keywords: complexity class random NC
zbMATH Keywords: parallel algorithm
MaRDI profile type: Publication
cites work: Fast probabilistic algorithms for Hamiltonian circuits and matchings
cites work: Parallel computation for well-endowed rings and space-bounded probabilistic machines
cites work: Fast parallel matrix and GCD computations
cites work: An overview of computational complexity
cites work: Systems of distinct representatives and linear algebra
cites work: Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
cites work: The maximum flow problem is log space complete for P
cites work: A Las Vegas RNC algorithm for maximum matching
cites work: Q3732972
cites work: Maximum matchings in general graphs through randomization
cites work: Fast Probabilistic Algorithms for Verification of Polynomial Identities
cites work: The Factors of Graphs
full work available at URL: https://doi.org/10.1007/bf02579407
OpenAlex ID: W2610729871
description: scientific article; zbMATH DE number 4053671