@article{4c34febb0a66409c8c7877404792c105,
title = "Faster optimal parallel prefix sums and list ranking",
abstract = "We present a parallel algorithm for the prefix sums problem which runs in time O( log n log log n) using n log log n log n processors (optimal speedup). This algorithm leads to a parallel list ranking algorithm which runs in O(log n) time using n log n processors (optimal speedup).",
author = "Richard Cole and Uzi Vishkin",
note = "Funding Information: * Research supported in part by NSF Grants DCR-84-01633 IBM faculty development award, by a John Simon Memorial ONR grant NOOO14-85-K-0046. {\textquoteright} Research supported in part by NSF Grants NSF-CCR-8615337 and NSF-DCR-8413359, ONR Grant NOOO14-85-K-0046, by the Applied Mathematical Science subprogram of office of Energy Research, U.S. Department of Energy under Contract DE-AC02-76ER03077, and by the Foundation for Research in Electronics, Computers and Communications. Administered by the Israel Academy of Sciences and Humanities.",
year = "1989",
month = jun,
doi = "10.1016/0890-5401(89)90036-9",
language = "English (US)",
volume = "81",
pages = "334--352",
journal = "Information and Computation",
issn = "0890-5401",
publisher = "Elsevier Inc.",
number = "3",
}