Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
An O(1) solution to the prefix sum problem on a specialized memory architecture
Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.
Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.
Faculty of Education, University of Primorska.
Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Embedded Internet Systems Lab.
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, p. 103-114Conference paper, Published paper (Refereed)
Abstract [en]

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. p. 103-114
National Category
Computer Sciences
Research subject
Dependable Communication and Computation Systems
Identifiers
URN: urn:nbn:se:ltu:diva-32407Local ID: 6e7788c0-96ca-11dc-ad7f-000ea68e967bISBN: 9780387346335 (print)OAI: oai:DiVA.org:ltu-32407DiVA, id: diva2:1005641
Conference
IFIP International Conference on Theoretical Computer Science : 01/08/2006 - 02/08/2006
Note

Godkänd; 2006; 20071119 (ysko)

Available from: 2016-09-30 Created: 2016-09-30 Last updated: 2018-02-23Bibliographically approved

Open Access in DiVA

fulltext(153 kB)118 downloads
File information
File name FULLTEXT01.pdfFile size 153 kBChecksum SHA-512
c7d1c156d510a131869ce3288953553cfac79e43e3f82bd0ae0381c5bfea0a841ba66b5c627352f8a671c1297d17ce544329fa819ebf29a508547c89106f5acc
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Brodnik, AndrejNilsson, Andreas
By organisation
Computer ScienceEmbedded Internet Systems Lab
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 118 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 245 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf