کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420527 | 683952 | 2014 | 5 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: An analysis of the size of the minimum dominating sets in random recursive trees, using the Cockayne–Goodman–Hedetniemi algorithm An analysis of the size of the minimum dominating sets in random recursive trees, using the Cockayne–Goodman–Hedetniemi algorithm](/preview/png/420527.png)
A random recursive tree on nn vertices is either a single isolated vertex (for n=1n=1) or is a vertex vnvn connected to a vertex chosen uniformly at random from a random recursive tree on n−1n−1 vertices. Such trees have been studied before [R. Smythe, H. Mahmoud, A survey of recursive trees, Theory of Probability and Mathematical Statistics 51 (1996) 1–29] as models of boolean circuits. More recently, Barabási and Albert [A. Barabási, R. Albert, Emergence of scaling in random networks, Science 286 (1999) 509–512] have used modifications of such models to model for the web and other “power-law” networks.A minimum (cardinality) dominating set in a tree can be found in linear time using the algorithm of Cockayne et al. [E. Cockayne, S. Goodman, S. Hedetniemi, A linear algorithm for the domination number of a tree, Information Processing Letters 4 (1975) 41–44]. We prove that there exists a constant d≃0.3745…d≃0.3745… such that the size of a minimum dominating set in a random recursive tree on nn vertices is dn+o(n)dn+o(n) with probability approaching one as nn tends to infinity. The result is obtained by analysing the algorithm of Cockayne, Goodman and Hedetniemi.
Journal: Discrete Applied Mathematics - Volume 157, Issue 9, 6 May 2009, Pages 2010–2014