SwePub
Sök i SwePub databas

  Utökad sökning

Träfflista för sökning "WFRF:(Miltersen Peter Bro) srt2:(1997-1999)"

Sökning: WFRF:(Miltersen Peter Bro) > (1997-1999)

  • Resultat 1-2 av 2
Sortera/gruppera träfflistan
   
NumreringReferensOmslagsbildHitta
1.
  • Andersson, Arne, et al. (författare)
  • Fusion trees can be implemented with AC0 instructions.
  • 1999
  • Ingår i: Theoretical Computer Science. ; 205, s. 337-344
  • Tidskriftsartikel (refereegranskat)abstract
    • Addressing a problem of Fredman and Willard, we implement fusion trees in deterministic linear space using AC^o instructions only. More precisely, we show that a subset of {0,...,2^(w-1)} of size n can be maintained using linear space under insertion, deletion, predecessor, and successor queries, with O(log n/loglog n) amortized time per operation on a RAM with word size w, where the only computational instructions allowed on the RAM are fuinctions in AC^0. The AC^0 instructions used are not all available on today's computers.
  •  
2.
  • Brodnik, Andrej, et al. (författare)
  • Trans-dichotomous algorithms without multiplication : some upper and lower bounds
  • 1997
  • Ingår i: Algorithms and Data Structures. - Berlin : Encyclopedia of Global Archaeology/Springer Verlag. - 9783540633075 ; , s. 426-439
  • Konferensbidrag (refereegranskat)abstract
    • 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.
  •  
Skapa referenser, mejla, bekava och länka
  • Resultat 1-2 av 2
Typ av publikation
konferensbidrag (1)
tidskriftsartikel (1)
Typ av innehåll
refereegranskat (2)
Författare/redaktör
Miltersen, Peter Bro (2)
Thorup, Mikkel (1)
Andersson, Arne (1)
Brodnik, Andrej (1)
Munro, J. Ian (1)
Lärosäte
Uppsala universitet (1)
Luleå tekniska universitet (1)
Språk
Engelska (2)
Forskningsämne (UKÄ/SCB)
Naturvetenskap (1)

År

Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.

 
pil uppåt Stäng

Kopiera och spara länken för att återkomma till aktuell vy