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:Inproceedings
Entered by:
TitleCombinatorial properties for efficient communication in distributed networks with local interactions
Bibtex cite IDRACTI-RU1-2009-104
Booktitle International Symposium on Parallel&Distributed Processing
Year published 2009
Location Italy
Note to appear
We investigate random intersection graphs, a combinatorial model that quite accurately abstracts distributed networks with local interactions between nodes blindly sharing critical resources from a limited globally available domain. We study important combinatorial properties (independence and hamiltonicity) of such graphs. These properties relate crucially to algorithmic design for important problems (like secure communication and frequency assignment) in distributed networks characterized by dense, local interactions and resource limitations, such as sensor networks. In particular, we prove that, interestingly, a small constant number of random, resource selections suffices to make the graph hamiltonian and we provide tight evaluations of the independence number of these graphs.
Nikoletseas, Sotiris
Raptopoulos, Christoforos
Spirakis, Paul
indurig.pdf (main file)
Publication ID789