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, 2 Jean-Claude König 1 Geneviève Simonet 3
1 APR - Algorithmes et Performance des Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
2 UM3 - Université Paul-Valéry - Montpellier 3
3 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)$.
Document type :
Conference papers
Complete list of metadatas

Cited literature [12 references]  Display  Hide  Download
https://hal-lirmm.ccsd.cnrs.fr/lirmm-00322361
Contributor : Benoit Darties <>
Submitted on : Wednesday, September 17, 2008 - 2:41:58 PM
Last modification on : Thursday, June 6, 2019 - 2:46:36 PM
Long-term archiving on : Thursday, June 3, 2010 - 7:54:23 PM

File

TCS2008-CDDKS.pdf
Files produced by the author(s)

Identifiers

Collections

APR | ALGCO | APR-LIRMM | LIRMM | MIPS | UNIV-MONTPELLIER | UNIV-MONTP3

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: Theoretical Computer Science, Sep 2008, Milan, Italy. pp.115-126, ⟨10.1007/978-0-387-09680-3_8⟩. ⟨lirmm-00322361⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

729

Files downloads

141

Contact

CCSD