• search hit 1 of 28
Back to Result List

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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
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
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.