Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • 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
Trans-dichotomous algorithms without multiplication: some upper and lower bounds
BRICS, Centre of the Danish National Research Foundation, University of Aarhus.
Department of Computer Science, University of Waterloo, Ontario.
1997 (English)In: Algorithms and Data Structures: 5th International Workshop, WADS'97 Halifax, Nova Scotia, Canada August 6-8, 1997 Proceedings / [ed] Frank Dehne; Andrew Rau-Chaplin; Jörg-Rüdiger Sack; Roberto Tamassia, Berlin: Encyclopedia of Global Archaeology/Springer Verlag, 1997, p. 426-439Conference paper, Published paper (Refereed)
Abstract [en]

We show that on a RAM with addition, subtraction, bitwise Boolean operations and shifts, but no multiplication, there is a transdichotomous solution to the static dictionary problem using linear space and with query time log n(log log n)1+0(1). On the way, we show that two w-bit words can be multiplied in time (log w)1+0(1) and that time (log w) is necessary, and that (log log w) time is necessary and sufficient for identifying the least significant set bit of a word.

Place, publisher, year, edition, pages
Berlin: Encyclopedia of Global Archaeology/Springer Verlag, 1997. p. 426-439
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 1272
National Category
Computer Sciences
Research subject
Dependable Communication and Computation Systems
Identifiers
URN: urn:nbn:se:ltu:diva-27065DOI: 10.1007/3-540-63307-3_80Local ID: 05fbf4f0-f0fe-11dc-ba03-000ea68e967bISBN: 978-3-540-63307-5 (print)OAI: oai:DiVA.org:ltu-27065DiVA, id: diva2:1000246
Conference
International Workshop on Algorithms and Data Structures : 06/08/1997 - 08/08/1997
Note
Godkänd; 1997; Bibliografisk uppgift: Session 11B: Invited Lecture; 20080313 (ysko)Available from: 2016-09-30 Created: 2016-09-30 Last updated: 2018-01-14Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Authority records BETA

Brodnik, Andrej

Search in DiVA

By author/editor
Brodnik, Andrej
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

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

Direct link
Cite
Citation style
  • apa
  • harvard1
  • 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