Best and worst case permutations for random online domination of the path
Copyright policy )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 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.Comment: 13 pages, 1 figure
Permutations, words, matrices, path graphs, mathematics - combinatorics, permutations, Randomized algorithms, random algorithms, graph domination, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), asymptotics, QA1-939, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Mathematics
Permutations, words, matrices, path graphs, mathematics - combinatorics, permutations, Randomized algorithms, random algorithms, graph domination, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), asymptotics, QA1-939, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Mathematics
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).0 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!