Главная

Angelika Steger

  1. On the Insertion Time of Cuckoo Hashing.

    Втр, 06/08/2010 - 15:01 — SomNambul
    Authors: Konstantinos Panagiotou, Angelika Steger, Nikolaos Fountoulakis
    Subjects: Data Structures and Algorithms
    Abstract

    Cuckoo 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.

  2. Extremal Subgraphs of Random Graphs: an Extended Version.

    Чт, 08/27/2009 - 13:23 — SomNambul
    Authors: Graham Brightwell, Konstantinos Panagiotou, Angelika Steger
    Subjects: Probability
    Abstract

    We 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).

  3. Extremal Subgraphs of Random Graphs: an Extended Version.

    Чт, 08/27/2009 - 13:23 — SomNambul
    Authors: Graham Brightwell, Konstantinos Panagiotou, Angelika Steger
    Subjects: Probability
    Abstract

    We 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).

Math-arch

RSS-материал