Best and worst case permutations for random online domination of the path
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...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2017-12-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/3278/pdf |
| _version_ | 1797270102641475584 |
|---|---|
| author | Christopher Coscia Jonathan DeWitt Fan Yang Yiguang Zhang |
| author_facet | Christopher Coscia Jonathan DeWitt Fan Yang Yiguang Zhang |
| author_sort | Christopher Coscia |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T01:58:56Z |
| format | Article |
| id | doaj.art-d24e385175ac423ba143625234e82b45 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T01:58:56Z |
| publishDate | 2017-12-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-d24e385175ac423ba143625234e82b452024-03-07T15:33:33ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502017-12-01Vol. 19 no. 2, Permutation...Permutation Patterns10.23638/DMTCS-19-2-23278Best and worst case permutations for random online domination of the pathChristopher CosciaJonathan DeWittFan YangYiguang ZhangWe 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.https://dmtcs.episciences.org/3278/pdfmathematics - combinatorics |
| spellingShingle | Christopher Coscia Jonathan DeWitt Fan Yang Yiguang Zhang Best and worst case permutations for random online domination of the path Discrete Mathematics & Theoretical Computer Science mathematics - combinatorics |
| title | Best and worst case permutations for random online domination of the path |
| title_full | Best and worst case permutations for random online domination of the path |
| title_fullStr | Best and worst case permutations for random online domination of the path |
| title_full_unstemmed | Best and worst case permutations for random online domination of the path |
| title_short | Best and worst case permutations for random online domination of the path |
| title_sort | best and worst case permutations for random online domination of the path |
| topic | mathematics - combinatorics |
| url | https://dmtcs.episciences.org/3278/pdf |
| work_keys_str_mv | AT christophercoscia bestandworstcasepermutationsforrandomonlinedominationofthepath AT jonathandewitt bestandworstcasepermutationsforrandomonlinedominationofthepath AT fanyang bestandworstcasepermutationsforrandomonlinedominationofthepath AT yiguangzhang bestandworstcasepermutationsforrandomonlinedominationofthepath |