Angelika Steger
On the Insertion Time of Cuckoo Hashing.
Tue, 06/08/2010 - 15:01 — SomNambulAuthors: Konstantinos Panagiotou, Angelika Steger, Nikolaos Fountoulakis
Subjects: Data Structures and Algorithms
AbstractCuckoo hashing is an efficient technique for creating large hash tables with
high space utilization and guaranteed constant access times. There, each item
can be placed in a location given by any one out of k different hash functions.
In this paper we investigate further the random walk heuristic for inserting in
an online fashion new items into the hash table.Extremal Subgraphs of Random Graphs: an Extended Version.
Thu, 08/27/2009 - 13:23 — SomNambulAuthors: Graham Brightwell, Konstantinos Panagiotou, Angelika Steger
Subjects: Probability
AbstractWe prove that there is a constant $c >0$, such that whenever $p \ge n^{-c}$,
with probability tending to 1 when $n$ goes to infinity, every maximum
triangle-free subgraph of the random graph $G_{n,p}$ is bipartite. This answers
a question of Babai, Simonovits and Spencer (Journal of Graph Theory, 1990).Extremal Subgraphs of Random Graphs: an Extended Version.
Thu, 08/27/2009 - 13:23 — SomNambulAuthors: Graham Brightwell, Konstantinos Panagiotou, Angelika Steger
Subjects: Probability
AbstractWe prove that there is a constant $c >0$, such that whenever $p \ge n^{-c}$,
with probability tending to 1 when $n$ goes to infinity, every maximum
triangle-free subgraph of the random graph $G_{n,p}$ is bipartite. This answers
a question of Babai, Simonovits and Spencer (Journal of Graph Theory, 1990).
User login
