research unit 1

Publication

Type of publication:Inproceedings
Entered by:
TitleSimple and Efficient Greedy Algorithms for Hamilton Cycles in Random Intersection Graphs
Bibtex cite IDRACTI-RU1-2005-4
Booktitle 16th Annual International Symposium on Algorithms and Computation (ISAAC 2005)
Year published 2005
Month December
Pages 493-504
URL http://www.cs.cityu.edu.hk/~isaac2005/
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.
Authors
Topics
BibTeXBibTeX
RISRIS
Attachments
 presentationISAAC05.pdf (main file) getPDF.pdf

Publication ID43