ANSV PROBLEM ON BSRS

Authors
XIANG LM USHIJIMA K
Citation
Lm. Xiang et K. Ushijima, ANSV PROBLEM ON BSRS, Information processing letters, 65(3), 1998, pp. 135-138
Citations number
10
Categorie Soggetti
Computer Science Information Systems","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
65
Issue
3
Year of publication
1998
Pages
135 - 138
Database
ISI
SICI code
0020-0190(1998)65:3<135:>2.0.ZU;2-7
Abstract
Optimal parallel algorithms for the ANSV (All Nearest Smaller Values) problem are known on CREW, CRCW, and EREW PRAMs, and on the Hypercube. In this paper, optimal parallel algorithms of constant time for the A NSV problem are discussed on BSR (broadcasting with selective reductio n), BSR with multiple criteria, and BSR+. The solution in this paper i s the first constant time solution to the ANSV problem on any model of computation. (C) 1998 Elsevier Science B.V.