research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Inproceedings
Entered by:
TitleExpander Properties and the Cover Time of Random Intersection Graphs
Bibtex cite IDRACTI-RU1-2007-16
Booktitle International Symposium on Mathematical Foundations of Computer Science (MFCS 2007)
Series Lecture Notes in Computer Science
Year published 2007
Month August
Volume 4708/2007
Pages 44-55
Publisher Springer Berlin / Heidelberg
Location Cesky Krumlov, CZech Republic
We investigate important combinatorial and algorithmic properties of $G_n, m, p$ random intersection graphs. In particular, we prove that with high probability (a) random intersection graphs are expanders, (b) random walks on such graphs are ``rapidly mixing" (in particular they mix in logarithmic time) and (c) the cover time of random walks on such graphs is optimal (i.e. it is $\Theta(n \logn)$). All results are proved for $p$ very close to the connectivity threshold and for the interesting, non-trivial range where random intersection graphs differ from classical $G_n, p$ random graphs.
Nikoletseas, Sotiris
Raptopoulos, Christoforos
Spirakis, Paul
fullpaper113.pdf (main file)
Short description of problem, previous work and result
Publication ID22