Abstract | In this work we consider the problem of finding Hamilton Cycles in graphs derived from the uniform random intersection graphs model $G_n, m, p$. In particular, (a) for the case $m = n^\alpha, \alpha>1$ we give a result that allows us to apply (with the same probability of success) any algorithm that finds a Hamilton cycle with high probability in a $G_n, k$ graph (i.e. a graph chosen equiprobably form the space of all graphs with $k$ edges), (b) we give an \textbfexpected polynomial time algorithm for the case $p = \textrmconstant$ and $m \leq \alpha \sqrt\fracn\logn$ for some constant $\alpha$, and (c) we show that the greedy approach still works well even in the case $m = o(\fracn\logn)$ and $p$ just above the connectivity threshold of $G_n, m, p$ (found in \citeSingerphd) by giving a greedy algorithm that finds a Hamilton cycle in those ranges of $m, p$ with high probability. |