Geodesic
Backbone colouring and algorithms for TDMA scheduling
Discrete mathematics & theoretical computer science, Tome 21 (2019) no. 3

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2019_21_3_a22,
     author = {Bensmail, Julien and Blanc, Thibaut and Cohen, Nathann and Havet, Fr\'ed\'eric and Rocha, Leonardo},
     title = {Backbone colouring and algorithms for {TDMA} scheduling},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {21},
     number = {3},
     year = {2019},
     doi = {10.23638/DMTCS-21-3-24},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-3-24/}
}
TY  - JOUR
AU  - Bensmail, Julien
AU  - Blanc, Thibaut
AU  - Cohen, Nathann
AU  - Havet, Frédéric
AU  - Rocha, Leonardo
TI  - Backbone colouring and algorithms for TDMA scheduling
JO  - Discrete mathematics & theoretical computer science
PY  - 2019
VL  - 21
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-3-24/
DO  - 10.23638/DMTCS-21-3-24
LA  - en
ID  - DMTCS_2019_21_3_a22
ER  - 
%0 Journal Article
%A Bensmail, Julien
%A Blanc, Thibaut
%A Cohen, Nathann
%A Havet, Frédéric
%A Rocha, Leonardo
%T Backbone colouring and algorithms for TDMA scheduling
%J Discrete mathematics & theoretical computer science
%D 2019
%V 21
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-3-24/
%R 10.23638/DMTCS-21-3-24
%G en
%F DMTCS_2019_21_3_a22
Bensmail, Julien; Blanc, Thibaut; Cohen, Nathann; Havet, Frédéric; Rocha, Leonardo. Backbone colouring and algorithms for TDMA scheduling. Discrete mathematics & theoretical computer science, Tome 21 (2019) no. 3. doi: 10.23638/DMTCS-21-3-24

Cité par Sources :