Name
Title | ||
|---|---|---|
Combinatorial properties for efficient communication in distributed networks with local interactions |
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1109/IPDPS.2009.5161002 | IPDPS |
Keywords | Field | DocType |
data mining,wireless sensor networks,probability density function,communication channels,cryptography,sensor network,secure communication,probabilistic logic,computer networks,distributed computing,construction industry,frequency,algorithm design,algorithm design and analysis,graph theory,distributed processing | Graph theory,Algorithm design,Computer science,Cryptography,Theoretical computer science,Probabilistic logic,Frequency assignment,Probability density function,Wireless sensor network,Secure communication,Distributed computing | Conference |
ISSN | Citations | PageRank |
1530-2075 | 3 | 0.43 |
References | Authors | |
12 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sotiris E. Nikoletseas | 1 | 1027 | 107.41 |
| Christoforos Raptopoulos | 2 | 192 | 22.39 |
| Paul G. Spirakis | 3 | 2222 | 299.05 |