The PDF file you selected should load here if your Web browser has a PDF reader plug-in installed (for example, a recent version of Adobe Acrobat Reader).

Alternatively, you can also download the PDF file directly to your computer, from where it can be opened using a PDF reader. To download the PDF, click the Download link below.

If you would like more information about how to print, save, and work with PDFs, Highwire Press provides a helpful Frequently Asked Questions about PDFs.

Download this PDF file Fullscreen Fullscreen Off

References

  1. T. Ali Khan and R. Neininger. Tail bounds for the Wiener index of random trees. In 2007 Conference on Analysis of Algorithms, AofA 07, 279-289, Discrete Math. Theor. Comput. Sci. Proc., AH, Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2007. MR2509528 (2010i:60027)
  2. F. Bergeron, P. Flajolet, B. Salvy. Varieties of increasing trees. CAAP '92 (Rennes, 1992), 24-48, Lecture Notes in Comput. Sci., 581, Springer, Berlin, 1992. MR1251994 (94j:68233)
  3. P. J. Bickel, D. A. Freedman. Some asymptotic theory for the bootstrap. Ann. Statist. 9 (1981), no. 6, 1196-1217. MR0630103 (83a:62051)
  4. N. Broutin and C. Holmgren. The total path length of split trees. preprint, 2011. http://arxiv.org/abs/1102.2541,
  5. V. Bruhn. Eine Methode zur asymptotischen Behandlung einer Klasse von Rekursionsgleichungen mit einer Anwendung in der stochastischen Analyse des Quicksort-Algorithmus. PhD thesis, University of Kiel, Germany, 1996.
  6. H.-H. Chern, H.-K. Hwang. Transitional behaviors of the average cost of Quicksort with median-of-(2t+1). Algorithmica 29 (2001), no. 1-2, 44-69. MR1887298 (2003k:68044)
  7. L. Devroye. Universal limit laws for depths in random trees. SIAM J. Comput. 28 (1999), no. 2, 409-432 (electronic). MR1634354 (2000e:68073)
  8. R. P. Dobrow, J. A. Fill. Total path length for random recursive trees. Combin. Probab. Comput. 8 (1999), no. 4, 317-333. MR1723646 (2000k:60016)
  9. L. C. Evans, R. F. Gariepy. Measure theory and fine properties of functions. CRC Press, Boca Raton, FL, 1992. MR1158660 (93f:28001)
  10. J. A. Fill, S. Janson. Quicksort asymptotics. J. Algorithms 44 (2002), no. 1, 4-28. MR1932675 (2003m:68032)
  11. P. Flajolet, G. Labelle, L. Laforest, B. Salvy. Hypergeometrics and the cost structure of quadtrees. Random Structures Algorithms 7 (1995), no. 2, 117-144. MR1369059 (96m:68034)
  12. D. Griffeath. A maximal coupling for Markov chains. Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 31 (1974/75), 95-106. MR0370771 (51 #6996)
  13. A. Gut. Stopped random walks. Limit theorems and applications. Springer-Verlag, New York, 1988. MR0916870 (88m:60085)
  14. C. Holmgren. Novel characteristics of split trees by use of renewal theory. 2010. submitted.
  15. S. Janson. The Wiener index of simply generated random trees. Random Structures Algorithms 22 (2003), no. 4, 337-358. MR1980963 (2004b:05186)
  16. H. M. Mahmoud. On the average internal path length of m-ary search trees. Acta Inform. 23 (1986), no. 1, 111-117. MR0845626 (87i:68008)
  17. H. M. Mahmoud, B. Pittel. Analysis of the space of search trees under the random insertion algorithm. J. Algorithms 10 (1989), no. 1, 52-75. MR0987097 (90a:68012)
  18. C. J. H. McDiarmid, R. B. Hayward. Large deviations for Quicksort. J. Algorithms 21 (1996), no. 3, 476-507. MR1417660 (97g:68052)
  19. G. O. Munsonius and L. Rüschendorf. Limit theorems for depths and distances in weighted random b-ary recursive trees. 2010. submitted.
  20. R. Neininger. On a multivariate contraction method for random recursive structures with applications to Quicksort. Random Structures Algorithms 19 (2001), no. 3-4, 498-524. MR1871564 (2002m:68020)
  21. R. Neininger. The Wiener index of random trees. Combin. Probab. Comput. 11 (2002), no. 6, 587-597. MR1940122 (2003k:05046)
  22. R. Neininger, L. Rüschendorf. On the internal path length of d-dimensional quad trees. Random Structures Algorithms 15 (1999), no. 1, 25-41. MR1698407 (2000h:60034)
  23. M. Régnier. A limiting distribution for quicksort. RAIRO Inform. Théor. Appl. 23 (1989), no. 3, 335-343. MR1020478 (90k:68132)
  24. U. Rösler. A limit theorem for "Quicksort". RAIRO Inform. Théor. Appl., 25 (1991), no. 1, 85-100. MR1104413 (92f:68028)
  25. U. Rösler. On the analysis of stochastic divide and conquer algorithms. Algorithmica 29 (2001), no. 1-2, 238-261. MR1887306 (2003b:68217)
Bookmark and Share


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.