Geodesic
Best and worst case permutations for random online domination of the path
Discrete mathematics & theoretical computer science, Permutation Patterns 2016, Tome 19 (2017-2018) no. 2

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

We study a randomized algorithm for graph domination, by which, according to a uniformly chosen permutation, vertices are revealed and added to the dominating set if not already dominated. We determine the expected size of the dominating set produced by the algorithm for the path graph $P_n$ and use this to derive the expected size for some related families of graphs. We then provide a much-refined analysis of the worst and best cases of this algorithm on $P_n$ and enumerate the permutations for which the algorithm has the worst-possible performance and best-possible performance. The case of dominating the path graph has connections to previous work of Bouwer and Star, and of Gessel on greedily coloring the path. 
@article{DMTCS_2018_19_2_a2,
     author = {Coscia, Christopher and DeWitt, Jonathan and Yang, Fan and Zhang, Yiguang},
     title = {Best and worst case permutations for random online domination of the path},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {19},
     number = {2},
     year = {2017-2018},
     doi = {10.23638/DMTCS-19-2-2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-2-2/}
}
TY  - JOUR
AU  - Coscia, Christopher
AU  - DeWitt, Jonathan
AU  - Yang, Fan
AU  - Zhang, Yiguang
TI  - Best and worst case permutations for random online domination of the path
JO  - Discrete mathematics & theoretical computer science
PY  - 2017-2018
VL  - 19
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-2-2/
DO  - 10.23638/DMTCS-19-2-2
LA  - en
ID  - DMTCS_2018_19_2_a2
ER  - 
%0 Journal Article
%A Coscia, Christopher
%A DeWitt, Jonathan
%A Yang, Fan
%A Zhang, Yiguang
%T Best and worst case permutations for random online domination of the path
%J Discrete mathematics & theoretical computer science
%D 2017-2018
%V 19
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-2-2/
%R 10.23638/DMTCS-19-2-2
%G en
%F DMTCS_2018_19_2_a2
Coscia, Christopher; DeWitt, Jonathan; Yang, Fan; Zhang, Yiguang. Best and worst case permutations for random online domination of the path. Discrete mathematics & theoretical computer science, Permutation Patterns 2016, Tome 19 (2017-2018) no. 2. doi: 10.23638/DMTCS-19-2-2

Cité par Sources :