publication . Preprint . 2020

Compaction for two models of logarithmic-depth trees: Analysis and Experiments

Bodini, Olivier; Genitrini, Antoine; Gittenberger, Bernhard; Larcher, Isabella; Naima, Mehdi;
Open Access English
  • Published: 26 May 2020
In this paper we are interested in the quantitative analysis of the compaction ratio for two classical families of trees: recursive trees and plane binary increasing tree. These families are typical representatives of tree models with a small depth. More formally, asymptotically, for a random tree with $n$ nodes, its depth is of order $\log n$. Once a tree of size $n$ is compacted by keeping only one occurrence of all fringe subtrees appearing in the tree the resulting graph contains only $O(n / \log n)$ nodes. This result must be compared to classical results of compaction in the families of simply generated trees, where the analog result states that the compac...
free text keywords: Mathematics - Combinatorics, Computer Science - Data Structures and Algorithms
Download from
19 references, page 1 of 2

[1] C. Bender and S. Orszag. Advanced Mathematical Methods for Scientists and Engineers: Asymptotic Methods and Perturbation Theory, volume 1. 1999.

[2] F. Bergeron, P. Flajolet, and B. Salvy. Varieties of increasing trees. In CAAP, pages 24-48, 1992. [OpenAIRE]

[3] O. Bodini, A. Genitrini, and F. Peschanski. A Quantitative Study of Pure Parallel Processes. Electronic Journal of Combinatorics, 23(1):P1.11, 39 pages, (electronic), 2016.

[4] M. Bousquet-Mélou, M. Lohrey, S. Maneth, and E. Noeth. XML compression via directed acyclic graphs. Theory of Computing Systems, 57(4):1322-1371, 2015.

[5] N. Broutin, L. Devroye, E. McLeish, and M. de la Salle. The height of increasing trees. Random Struct. Algorithms, 32(4):494-518, 2008. [OpenAIRE]

[6] M. Drmota. An analytic approach to the height of binary search trees II. J. ACM, 50(3):333-374, 2003. [OpenAIRE]

[7] M. Drmota. Random trees. Springer, Vienna-New York, 2009. [OpenAIRE]

[8] M. Drmota, A. Iksanov, M. Moehle, and U. Roesler. A limiting distribution for the number of cuts needed to isolate the root of a random recursive tree. Random Struct. Algorithms, 34(3):319-336, 2009.

[9] P. Flajolet and R. Sedgewick. Analytic Combinatorics. Cambridge University Press, 2009.

[10] P. Flajolet, P. Sipala, and J.-M. Steyaert. Analytic variations on the common subexpression problem. In Automata, languages and programming (Coventry, 1990), volume 443 of Lecture Notes in Comput. Sci., pages 220-234. Springer, New York, 1990.

[11] E. L. Ince. Ordinary Differential Equations. Dover Publications, New York, 1944.

[12] D. E. Knuth. The art of computer programming, volume 3: (2nd ed.) sorting and searching. Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, USA, 1998.

[13] M. Kuba and A. Panholzer. On the degree distribution of the nodes in increasing trees. J. Comb. Theory, Ser. A, 114(4):597-618, 2007. [OpenAIRE]

[14] H. M. Mahmoud and R. T. Smythe. A Survey of Recursive Trees. Theo. Probability and Mathematical Statistics, 51:1-37, 1995. [OpenAIRE]

[15] A. Meir and J. Moon. On the altitude of nodes in random trees. Canadian Journal of Mathematics, 30:997- 1015, 1978. [OpenAIRE]

19 references, page 1 of 2
Powered by OpenAIRE Open Research Graph
Any information missing or wrong?Report an Issue