Title :
An optimal parallel minimax tree algorithm
Author :
Kirkpatrick, D.G. ; Przytycka, T.
Author_Institution :
British Columbia Univ., Vancouver, BC, Canada
Abstract :
An log n time n/log n processor CREW PRAM algorithm to construct an alphabetic minimax tree is presented. The algorithm achieves these optimal bounds by a combination of existing parallel techniques (applied in novel ways) and a new technique, called accelerated valley filling. Parallel algorithms for several other versions of the minimax tree problem are also discussed
Keywords :
computational complexity; minimax techniques; parallel algorithms; trees (mathematics); CREW PRAM algorithm; accelerated valley filling; alphabetic minimax tree; optimal bounds; optimal parallel minimax tree algorithm; Acceleration; Algorithm design and analysis; Binary search trees; Binary trees; Computer science; Cost function; Filling; Minimax techniques; Parallel algorithms; Phase change random access memory;
Conference_Titel :
Parallel and Distributed Processing, 1990. Proceedings of the Second IEEE Symposium on
Conference_Location :
Dallas, TX
Print_ISBN :
0-8186-2087-0
DOI :
10.1109/SPDP.1990.143551
