Startseite > Publikationen > Publikationen

Publikationen

Borodin, Allan;Fich, Faith;Meyer auf der Heide, Friedhelm;Upfal, Eli;Wigderson, Avi:

A Tradeoff Between Search and Update Time for the Implicit Dictionary Problem.

ICALP 1986 : S. 50-59, Jul. 1986

Abstract

This paper proves a tradeoff between the time it makes to search for elements in an implicit dictionary and the time it takes to update the value of elements in specified locations of the dictionary. It essentially shows that if the update time is constant, then the search time ist Ω(n^ε) for some constant &epsilon > 0.

Dateien

hni1931.pdf



Bibtex

@article{hniid=1931,
author = {Borodin, Allan and Fich, Faith and Meyer auf der Heide, Friedhelm and Upfal, Eli and Wigderson, Avi},
title = {A Tradeoff Between Search and Update Time for the Implicit Dictionary Problem},
journal = {ICALP 1986},
pages = {50-59},
month = jul,
year = {1986},
}

BibTeX in die Zwischenablage kopieren

Permalink

https://www.hni.uni-paderborn.de/pub/1931