A Note on Node Coloring in the SINR Model
Type de document :
Rapport de recherche: Autre communication scientifique (congrès sans actes - poster - séminaire...)
Titre :
A Note on Node Coloring in the SINR Model
Auteur(s) :
Derbel, Bilel [Auteur correspondant]
Laboratoire d'Informatique Fondamentale de Lille [LIFL]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Talbi, El-Ghazali [Auteur]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Laboratoire d'Informatique Fondamentale de Lille [LIFL]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Talbi, El-Ghazali [Auteur]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Institution :
INRIA
Date de publication :
2009
Discipline(s) HAL :
Informatique [cs]/Calcul parallèle, distribué et partagé [cs.DC]
Résumé en anglais : [en]
A $\xi$-coloring of a graph $G$ is a coloring of the nodes of $G$ with $\xi$ colors in such a way any two neighboring nodes have different colors. We prove that there exists a $O(\Delta \log n)$ time distributed algorithm ...
Lire la suite >A $\xi$-coloring of a graph $G$ is a coloring of the nodes of $G$ with $\xi$ colors in such a way any two neighboring nodes have different colors. We prove that there exists a $O(\Delta \log n)$ time distributed algorithm computing a $O(\Delta)$-colroing for unit disc graphs under the signal-to-interference-plus-noise ratio (SINR)-based physical model ($\Delta$ is the maximum degree of the graph). We also show that, for a well defined constant $d$, a $d$-hop $O(\Delta)$-coloring allows us to schedule an interference free MAC protocol under the physical SINR constraints. For instance this allows us to prove that any point-to-point message passing algorithm with running time $\tau$ can be simulated in the SINR model in $O(\Delta (\log n + \tau))$ time using messages of well chosen size. All our algorithms are proved to be correct with high probability.Lire moins >
Lire la suite >A $\xi$-coloring of a graph $G$ is a coloring of the nodes of $G$ with $\xi$ colors in such a way any two neighboring nodes have different colors. We prove that there exists a $O(\Delta \log n)$ time distributed algorithm computing a $O(\Delta)$-colroing for unit disc graphs under the signal-to-interference-plus-noise ratio (SINR)-based physical model ($\Delta$ is the maximum degree of the graph). We also show that, for a well defined constant $d$, a $d$-hop $O(\Delta)$-coloring allows us to schedule an interference free MAC protocol under the physical SINR constraints. For instance this allows us to prove that any point-to-point message passing algorithm with running time $\tau$ can be simulated in the SINR model in $O(\Delta (\log n + \tau))$ time using messages of well chosen size. All our algorithms are proved to be correct with high probability.Lire moins >
Langue :
Anglais
Collections :
Source :
Fichiers
- https://hal.inria.fr/inria-00408670v4/document
- Accès libre
- Accéder au document
- https://hal.inria.fr/inria-00408670v4/document
- Accès libre
- Accéder au document
- https://hal.inria.fr/inria-00408670v4/document
- Accès libre
- Accéder au document
- document
- Accès libre
- Accéder au document
- RR-7058.pdf
- Accès libre
- Accéder au document