id: 05970648
dt: a
an: 05970648
au: Nikoletseas, Sotiris; Raptopoulos, Christoforos; Spirakis, Paul G.
ti: Selected combinatorial properties of random intersection graphs.
so: Kuich, Werner (ed.) et al., Algebraic foundations in computer science.
    Essays dedicated to Symeon Bozapalidis on the occasion of his
    retirement. Berlin: Springer (ISBN 978-3-642-24896-2/pbk). Lecture
    Notes in Computer Science 7020, 347-362 (2011).
py: 2011
pu: Berlin: Springer
la: EN
cc: 
ut: 
ci: 
li: doi:10.1007/978-3-642-24897-9_15
ab: Summary: Consider a universal set ${\cal M}$ and a vertex set $V$ and
    suppose that to each vertex in $V$ we assign independently a subset of
    ${\cal M}$ chosen at random according to some probability distribution
    over subsets of ${\cal M}$. By connecting two vertices if their
    assigned subsets have elements in common, we get a random instance of a
    random intersection graphs model. In this work, we overview some
    results concerning the existence and efficient construction of Hamilton
    cycles in random intersection graph models. In particular, we present
    and discuss results concerning two special cases where the assigned
    subsets to the vertices are formed by (a) choosing each element of
    ${\cal M}$ independently with probability $p$ and (b) selecting
    uniformly at random a subset of fixed cardinality.
rv: