Expander properties and the cover time of random intersection graphs

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

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2009-11, Vol.410 (50), p.5261-5272
Main Authors: Nikoletseas, S., Raptopoulos, C., Spirakis, P.G.
Format: Article
Language:English
Subjects:
Cover time
Expansion
Mixing time
Random intersection graphs
Random walks
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 Θ ( n log n ) ). 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.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2009.08.028