HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

Backbone colouring and algorithms for TDMA scheduling

Julien Bensmail 1 Thibaut Blanc 2 Nathann Cohen 3 Frédéric Havet 1 Leonardo Rocha 4
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
3 GALaC - LRI - Graphes, Algorithmes et Combinatoire (LRI)
LRI - Laboratoire de Recherche en Informatique
Abstract : We investigate graph colouring models for the purpose of optimizing TDMA link scheduling in Wireless Networks. Inspired by the BPRN-colouring model recently introduced by Rocha and Sasaki, we introduce a new colouring model, namely the BMRN-colouring model, which can be used to model link scheduling problems where particular types of collisions must be avoided during the node transmissions. In this paper, we initiate the study of the BMRN-colouring model by providing several bounds on the minimum number of colours needed to BMRN-colour digraphs, as well as several complexity results establishing the hardness of finding optimal colourings. We also give a special focus on these considerations for planar digraph topologies, for which we provide refined results.
Document type :
Journal articles
Complete list of metadata

Cited literature [28 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-01851600
Contributor : Julien Bensmail Connect in order to contact the contributor
Submitted on : Thursday, June 20, 2019 - 1:40:52 PM
Last modification on : Friday, January 21, 2022 - 3:12:04 AM

File

bmrn-dmtcs.pdf
Files produced by the author(s)

Identifiers

Citation

Julien Bensmail, Thibaut Blanc, Nathann Cohen, Frédéric Havet, Leonardo Rocha. Backbone colouring and algorithms for TDMA scheduling. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2019, Vol. 21 no. 3 (3), pp.#24. ⟨10.23638/DMTCS-21-3-24⟩. ⟨hal-01851600v4⟩

Share

Metrics

Record views

357

Files downloads

537