An O(1) solution to the prefix sum problem on a specialized memory architecture
2006 (English)In: PFourth IFIP International Conference on Theoretical Computer Science - TCS 2006: IFIP 19th World Computer Congress, TC-1, Foundations of Computer Science, August 23-24, 2006, Santiago, Chile / [ed] Gonzalo Navarro; Leopoldo Bertossi; Yoshiharu Kohayakawa, New York: Encyclopedia of Global Archaeology/Springer Verlag, 2006, 103-114 p.Conference paper (Refereed)
In this paper we study the Prefix Sum problem introduced by Fredman. We show that it is possible to perform both update and retrieval in O(1) time simultaneously under a memory model in which individual bits may be shared by several words. We also show that two variants (generalizations) of the problem can be solved optimally in Θ(lgN) time under the comparison based model of computation.
Place, publisher, year, edition, pages
New York: Encyclopedia of Global Archaeology/Springer Verlag, 2006. 103-114 p.
Research subject Dependable Communication and Computation Systems
IdentifiersURN: urn:nbn:se:ltu:diva-32407Local ID: 6e7788c0-96ca-11dc-ad7f-000ea68e967bISBN: 9780387346335OAI: oai:DiVA.org:ltu-32407DiVA: diva2:1005641
IFIP International Conference on Theoretical Computer Science : 01/08/2006 - 02/08/2006
Godkänd; 2006; 20071119 (ysko)2016-09-302016-09-30Bibliographically approved