Colouring random intersection graphs and complex networks
Please always quote using this URN:urn:nbn:de:0296-matheon-3087
- Random intersection graphs naturally exhibit a certain amount of transitivity and hence can be used to model real--world networks. We study the evolution of the chromatic number of a random intersection graph and show that, in a certain range of parameters, these random graphs can be coloured optimally with high probability using different greedy algorithms. Experiments on real network data confirm the positive theoretical predictions and suggest that heuristics for the clique and the chromatic number can work hand in hand proving mutual optimality.
Author: | Michael Behrisch, Anusch Taraz, Michael Ueckerdt |
---|---|
URN: | urn:nbn:de:0296-matheon-3087 |
Referee: | Hans Jürgen Prömel |
Document Type: | Preprint, Research Center Matheon |
Language: | English |
Date of first Publication: | 2006/09/01 |
Release Date: | 2005/09/12 |
Tag: | |
Institute: | Humboldt-Universität zu Berlin |
Preprint Number: | 305 |