7 documents found

Proceedings
CC BY 3.0
2017-12-19

Theory and applications of hashing : report from Dagstuhl Seminar 17181

This report documents the program and the topics discussed of the 4-day Dagstuhl Seminar 17181 “Theory and Applications of Hashing”, which took place May 1–5, 2017. Four long and eighteen short talks covered a wide and diverse range of topics within the theme of the workshop. The program left sufficient...
Wadern: Schloss Dagstuhl, 2017-12-19
Book chapter
CC BY 3.0
2017-12-19

Cuckoo hashing with overlapping buckets

Wadern: Schloss Dagstuhl, 2017-12-19
Proceedings
CC BY 3.0
2016-06

15th Scandinavian Symposium and Workshops on Algorithm Theory : SWAT 2016, Jun ...

Saarbrücken/Wadern: Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing, 2016-06
Book chapter
CC BY 3.0
2016-06

Linear-time recognition of map graphs with outerplanar witness

Map graphs generalize planar graphs and were introduced by Chen, Grigni and Papadimitriou [STOC 1998, J.ACM 2002]. They showed that the problem of recognizing map graphs is in NP by proving the existence of a planar witness graph W. Shortly after, Thorup [FOCS 1998] published a polynomial-time recognition...
Saarbrücken/Wadern: Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing, 2016-06
Dissertation
2015-07-29

On the Analysis of Two Fundamental Randomized Algorithms - Multi-Pivot...

Im ersten Teil der vorliegenden Arbeit werden Multi-Pivot-Quicksort-Algorithmenbetrachtet. Die Idee mehr als ein Pivotelement im Quicksort-Algorithmus zunutzen, erschien über viele Jahre als unpraktikabel. Dies änderte sich, als imJahr 2009 ein Dual-Pivot-Algorithmus von V. Yaroslavskiy zumStandard-Sortierverfahren...
Dissertation
2015-05-06

Thresholds for Matchings in Random Bipartite Graphs with Applications to...

Wir betrachten randomisierte Algorithmen, die bei Eingabe einer Menge S von n Schlüsseln aus einem Universum U,oder einer Menge von n Schlüssel-Wert-Paaren eine Datenstruktur für eine der folgenden Aufgaben bauen.Bei Aufruf der Operation lookup für einen Schlüssel x aus U: * Entscheide, ob x Element...
Dissertation
2009-10-05

On Risks of Using a High Performance Hashing Scheme with Common Universal...

The contribution of this thesis is a mathematical analysis a high performance hashing scheme called cuckoo hashing when combined with two very simple and efficient classes of functions that we refer to as the multiplicative class and the linear class, respectively. We prove that cuckoo hashing tends...