Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6876245 | Theoretical Computer Science | 2014 | 23 Pages |
Abstract
This paper concerns constructing independent sets in a random intersection graph. We concentrate on two cases of the model: a binomial and a uniform random intersection graph. For both models we analyse two greedy algorithms and prove that they find asymptotically almost optimal independent sets. We provide detailed analysis of the presented algorithms and give tight bounds on the independence number for the studied models. Moreover we determine the range of parameters for which greedy algorithms give better results for a random intersection graph than this is in the case of an ErdÅs-Rényi random graph G(n,pË).
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Katarzyna Rybarczyk,