The MV-Decomposition: Definition and Application to the Distance-2 Broadcast Problem in Multi-Hops Radio Networks

Benoit Darties 1 Olivier Cogis 1 Sylvain Durand 1 Jean-Claude König 1 Geneviève Simonet 2
1 APR - Algorithmes et Performance des Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
2 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : We present a new tool called the "mv- decomposition", and we describe some interesting algorithmic properties about it. We propose an algorithm with a complexity of $O(m)$ to build a mv-decomposition for each bipartite graph. We use this mv-decomposition to propose a solution to the distance-2 broadcast problem in a synchronous multi-hops radio networks where adjacent transmissions are subject to interferences. More precisely, we propose two algorithms of resolution: the first one guarantees a complete distance-2 broadcast scheme using $O((log n )2)$ slots for a time complexity of $O (m (log n)2)$, while the second builds a solution with a minimal number of transmissions for a time complexity of $O(m)$.
Type de document :
Communication dans un congrès
TCS'08: 5th International Conference on Theoretical Computer Science, Sep 2008, Milan, Italy. IFIP, pp.115-126, 2008
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00322361
Contributeur : Benoit Darties <>
Soumis le : mercredi 17 septembre 2008 - 14:41:58
Dernière modification le : vendredi 9 juin 2017 - 10:41:26
Document(s) archivé(s) le : jeudi 3 juin 2010 - 19:54:23

Fichier

TCS2008-CDDKS.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : lirmm-00322361, version 1

Collections

APR | ALGCO | APR-LIRMM | LIRMM | MIPS

Citation

Benoit Darties, Olivier Cogis, Sylvain Durand, Jean-Claude König, Geneviève Simonet. The MV-Decomposition: Definition and Application to the Distance-2 Broadcast Problem in Multi-Hops Radio Networks. TCS'08: 5th International Conference on Theoretical Computer Science, Sep 2008, Milan, Italy. IFIP, pp.115-126, 2008. <lirmm-00322361>

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de
la notice

307

Téléchargements du document

103

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD