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:Article
Entered by:chita
TitleThe existence and Efficient Construction of Large Independent Sets in General Random Intersection Graphs
Bibtex cite IDRACTI-RU1-2004-45
Journal Theoretical Computer Science (TCS)
Year published 2004
Month July
Volume 3142/2004
Pages 1029-1040
ISSN 0302-9743
Note Special Issue on Algorithmic Aspects of Global Computing
DOI 10.1007/b99859
We investigate the existence and efficient algorithmic construction of close to optimal independent sets in random models of intersection graphs. In particular, (a) we propose a new model for random intersection graphs (Gn,m,p) which includes the model of [10] (the “uniform” random intersection graphs model) as an important special case. We also define an interesting variation of the model of random intersection graphs, similar in spirit to random regular graphs. (b) For this model we derive exact formulae for the mean and variance of the number of independent sets of size k (for any k) in the graph. (c) We then propose and analyse three algorithms for the efficient construction of large independent sets in this model. The first two are variations of the greedy technique while the third is a totally new algorithm. Our algorithms are analysed for the special case of uniform random intersection graphs. Our analyses show that these algorithms succeed in finding close to optimal independent sets for an interesting range of graph parameters.
Nikoletseas, Sotiris
Raptopoulos, Christoforos
Spirakis, Paul
getPDF.pdf (main file)
Publication ID166