DocumentCode :
3162874
Title :
On a fast deterministic parallel approximate matching algorithm
Author :
Haglin, David J.
Author_Institution :
Dept. of Comput. & Inf. Sci., Mankato State Univ., MN, USA
fYear :
1991
fDate :
2-5 Dec 1991
Firstpage :
774
Lastpage :
777
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(k5log4n) parallel time using O(2kn2k+2) processors on a CREW PRAM parallel machine model. The approximation is at least as big as k/k+1.|Mˆ|. If the allowed error is a constant, then the algorithm runs in polylogarithmic time using a polynomial number of processors
Keywords :
approximation theory; computational complexity; parallel algorithms; random-access storage; CREW PRAM parallel machine model; approximation scheme; cardinality matching problem; deterministic parallel approximate matching algorithm; sublinear parallel graph matching algorithms; Approximation algorithms; Bipartite graph; Concurrent computing; Costs; Parallel algorithms; Parallel machines; Phase change random access memory; Terminology;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Parallel and Distributed Processing, 1991. Proceedings of the Third IEEE Symposium on
Conference_Location :
Dallas, TX
Print_ISBN :
0-8186-2310-1
Type :
conf
DOI :
10.1109/SPDP.1991.218242
Filename :
218242
Link To Document :
https://search.ricest.ac.ir/dl/search/defaultta.aspx?DTC=49&DC=3162874
بازگشت