@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",

}