The MV-Decomposition: Definition and Application to the Distance-2 Broadcast Problem in Multi-Hops Radio Networks - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2008

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

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)$.
Fichier principal
Vignette du fichier
TCS2008-CDDKS.pdf (78.54 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

lirmm-00322361 , version 1 (17-09-2008)

Identifiers

Cite

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⟩
378 View
175 Download

Altmetric

Share

More