<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 12 Issue 1" %>
Isolating a Leaf in Rooted Trees via Random Cuttings
Markus Kuba and Alois Panholzer
Institut für Diskrete Mathematik und Geometrie, Technische UniversitätWien,Wiedner Hauptstr. 8-10/104, 1040 Wien, Austria
{Markus.Kuba, Alois.Panholzer}@tuwien.ac.at
Annals of Combinatorics 12 (1) p.81-99 March, 2008
AMS Subject Classification:05C05, 05A16, 60F05
We consider a recursive procedure for destroying rooted trees and isolating a leaf by removing a random edge and keeping the subtree, which does not contain the original root. For two tree families, the simply generated tree families and increasing tree families, we study here the number of random cuts that are necessary to isolate a leaf. We can show limiting distribution results of this parameter for simply generated trees and certain increasing trees.
Keywords: simply generated trees, recursive trees, cutting-down procedure, node isolation, limiting distribution


1. D. Aldous, The continuum random tree II: an overview, London Math. Soc. Lecture Note Ser. 167 (1991) 23-70.

2. M. Abramowitz and I. Stegun, Handbook of Mathematical Functions, 9th Edit., Dover, New York, 1970.

3. F. Bergeron, P. Flajolet, and B. Salvy, Varieties of increasing trees, Lecture Notes in Comput. Sci. 581 (1992) 24-48.

4. K.L. Chung, A Course in Probability Theory, Academic Press, San Diego, 1974.

5. M. Drmota, A. Iksanov, M. Möhle, and U. Rösler, A limiting distribution for the number of cuts needed to isolate the root of a random recursive tree, Random Structures Algorithms, preprint.

6. M. Drmota, A. Iksanov, M. Möhle, and U. Rösler, Asymptotic results about the total branch length of the Bolthausen-Sznitman coalescent, Stochastic Process. Appl. 117 (10) (2007) 1404-1421.

7. J.A. Fill, N. Kapur, and A. Panholzer, Destruction of very simple trees, Algorithmica 46 (3-4) (2006) 345-366.

8. J.A. Fill, H. Mahmoud, and W. Szpankowski, On the distribution for the duration of a randomized leader election algorithm, Ann. Appl. Probab. 6 (4) (1996) 1260-1283.

9. P. Flajolet and A. Odlyzko, The average height of binary trees and other simple trees, J. Comput. System Sci. 25 (2) (1982) 171-213.

10. P. Flajolet and A. Odlyzko, Singularity analysis of generating functions, SIAM J. Discrete Math. 3 (2) (1990) 216-240.

11. M. Hoffman, Multiple harmonic series, Pacific J. Math. 152 (2) (1992) 275-290.

12. S. Janson, Random cutting and records in deterministic and random trees, Random Structures Algorithms 29 (2) (2006) 139-179.

13. S. Janson and W. Szpankowski, Analysis of an asymmetric leader election algorithm, Electron. J. Combin. 4 (1) (1997) #R17.

14. D. Knuth and A. Schönhage, The expected linearity of a simple equivalence algorithm, Theoret. Comput. Sci. 6 (3) (1978) 281-315.

15. H. Mahmoud, Evolution of Random Search Trees, John Wiley & Sons , New York, 1992.

16. H. Mahmoud and R. Smythe, A survey of recursive trees, Theory Probab. Math. Statist. 51 (1995) 1-37.

17. A. Meir and J.W. Moon, Cutting down random trees, J. Austral. Math. Soc. 11 (1970) 313- 324.

18. A. Meir and J.W. Moon, Cutting down recursive trees, Math. Biosci. 21 (1974) 173-181.

19. A. Meir and J.W. Moon, On the altitude of nodes in random trees, Canad. J. Math. 30 (5) (1978) 997-1015.

20. R. Neininger and L. Rüschendorf, On the contraction method with degenerate limit equation, Ann. Probab. 32 (3B) (2004) 2838-2856.

21. A. Panholzer, Non-crossing trees revisited: cutting down and spanning subtrees, In: Discrete Random Walks, C. Banderier and C. Krattenthaler Eds., Discrete Math. Theoret. Comput. Sci., Proceedings AC, (2003) pp. 265-276.

22. A. Panholzer, Destruction of recursive trees, In: Proceedings of the “Third Colloquium on Mathematics and Computer Science”, M. Drmota et al. Eds., Birkhäuser, Basel, (2004) pp. 267-280.

23. A. Panholzer, The climbing depth of random trees, Random Structures Algorithms 26 (1-2) (2005) 84-109.

24. A. Panholzer, Cutting down very simple trees, Quaest. Math. 29 (2006) (2) 211-227.

25. H. Prodinger, How to select a loser, Discrete Math. 120 (1-3) (1993) 149-159.

26. U. Rösler, On the analysis of stochastic divide and conquer algorithms, Algorithmica 29 (1-2) (2001) 238-261.

27. J. Vitter and P. Flajolet, Average case analysis of algorithms and data structures, In: Handbook of Theoretical Computer Science, Vol. A, Elsevier, Amsterdam, (1990) pp. 431-524.