Deterministic parallel list ranking |
| |
| Authors: | Richard J. Anderson and Gary L. Miller |
| |
| Affiliation: | (1) Department of Computer Science, FR-35, University of Washington, 98195 Seattle, WA, USA;(2) Department of Computer Science, University of Southern California, 90089 Los Angeles, CA, USA |
| |
| Abstract: | In this paper we describe a simple parallel algorithm for list ranking. The algorithm is deterministic and runs inO(logn) time on an EREW PRAM withn/logn processors. The algorithm matches the performance of the Cole-Vishkin [CV3] algorithm but is simple and has reasonable constant factors.R. J. Anderson was supported by an NSF Presidential Young Investigator award and G. L. Miller was supported by NSF Grant DCR-85114961. |
| |
| Keywords: | List ranking Parallel algorithms List traversal |
| 本文献已被 SpringerLink 等数据库收录！ |
|
