Geodesic
A Linear-Time Optimal Broadcasting Algorithm in Stars of Cliques
Peter Damaschke1
1 Chalmers University of Technology and University of Gothenburg
Journal of Graph Algorithms and Applications, Tome 28 (2024) no. 1, pp. 385-388.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

For the telephone broadcast model, an $O(n\log n)$-time algorithm for constructing an optimal broadcasting scheme in a star of cliques with a total of $n$ vertices was recently presented by Ambashankar and Harutyunyan at IWOCA 2024. In the present note we give a considerably shorter and purified algorithm description and correctness proof. Moreover, we improve the time complexity to $O(n)$.
DOI : 10.7155/jgaa.v28i1.2981
Keywords: telephone broadcast, star of cliques, optimal algorithm

Peter Damaschke 1

1 Chalmers University of Technology and University of Gothenburg 
@article{JGAA_2024_28_1_a15,
     author = {Peter Damaschke},
     title = {A {Linear-Time} {Optimal} {Broadcasting} {Algorithm} in {Stars} of {Cliques}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {385--388},
     publisher = {mathdoc},
     volume = {28},
     number = {1},
     year = {2024},
     doi = {10.7155/jgaa.v28i1.2981},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i1.2981/}
}
TY  - JOUR
AU  - Peter Damaschke
TI  - A Linear-Time Optimal Broadcasting Algorithm in Stars of Cliques
JO  - Journal of Graph Algorithms and Applications
PY  - 2024
SP  - 385
EP  - 388
VL  - 28
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i1.2981/
DO  - 10.7155/jgaa.v28i1.2981
LA  - en
ID  - JGAA_2024_28_1_a15
ER  - 
%0 Journal Article
%A Peter Damaschke
%T A Linear-Time Optimal Broadcasting Algorithm in Stars of Cliques
%J Journal of Graph Algorithms and Applications
%D 2024
%P 385-388
%V 28
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i1.2981/
%R 10.7155/jgaa.v28i1.2981
%G en
%F JGAA_2024_28_1_a15
Peter Damaschke. A Linear-Time Optimal Broadcasting Algorithm in Stars of Cliques. Journal of Graph Algorithms and Applications, Tome 28 (2024) no. 1, pp. 385-388. doi : 10.7155/jgaa.v28i1.2981. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i1.2981/

Cité par Sources :