Paper Info
Title
On a fast deterministic parallel approximate matching algorithm
Abstract
Sublinear parallel graph matching algorithms are investigated. The author proposes an approximation scheme for the cardinality matching problem on general graphs that runs in O(k/sup 5/log/sup 4/n) parallel time using O(2/sup k/n/sup 2k+2/) processors on a CREW PRAM parallel machine model. The approximation is at least as big as /sup k///sub k+1/. mod M mod . If the allowed error is a constant, then the algorithm runs in polylogarithmic time using a polynomial number of processors.
Year
DOI
Venue
1991
10.1109/SPDP.1991.218242
Dallas, TX
Keywords
Field
DocType
bipartite graph,concurrent computing,approximation algorithms,parallel algorithm,approximation theory,terminology,computational complexity,graph matching,parallel algorithms
Sublinear function,Approximation algorithm,Polynomial,Computer science,Parallel algorithm,Bipartite graph,Cardinality,Algorithm,Matching (graph theory),Distributed computing,Computational complexity theory
Conference
ISBN
Citations 
PageRank 
0-8186-2310-1
0
0.34
References 
Authors
6
1
Name
Order
Citations
PageRank
David J. Haglin111219.45