• search hit 1 of 18
Back to Result List

On bucket increasing trees, clustered increasing trees and increasing diamonds

  • In this work we analyse bucket increasing tree families. We introduce two simple stochastic growth processes, generating random bucket increasing trees of size n, complementing the earlier result of Mahmoud and Smythe (1995, Theoret. Comput. Sci.144 221–249.) for bucket recursive trees. On the combinatorial side, we define multilabelled generalisations of the tree families d-ary increasing trees and generalised plane-oriented recursive trees. Additionally, we introduce a clustering process for ordinary increasing trees and relate it to bucket increasing trees. We discuss in detail the bucket size two and present a bijection between such bucket increasing tree families and certain families of graphs called increasing diamonds, providing an explanation for phenomena observed by Bodini et al. (2016, Lect. Notes Comput. Sci.9644 207–219.). Concerning structural properties of bucket increasing trees, we analyse the tree parameter Kn . It counts the initial bucket size of the node containing label n in a tree of size n and is closely related to the distribution of node types. Additionally, we analyse the parameters descendants of label j and degree of the bucket containing label j, providing distributional decompositions, complementing and extending earlier results (Kuba and Panholzer (2010), Theoret. Comput. Sci.411(34–36) 3255–3273.).

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Markus Kuba, Alois Panholzer
Parent Title (English):Combinatorics, Probability and Computing
Document Type:Article
Language:English
Completed Date:2022/07/01
Date of first Publication:2021/10/13
Responsibility for metadata:Fachhochschule Technikum Wien
Release Date:2023/01/01
GND Keyword:bucket-increasing-trees; clustered-trees; descendants; nodedegrees; stochastic-growth-processes
Issue:Volume 31 , Issue 4
First Page:629
Last Page:661
Publish on Website:1
Open Access:0
Reviewed:0
Link to Publication:doi:10.1017/S0963548321000493
Department:Department Angewandte Mathematik und Physik
Research Focus:Sonstiges
Projects:Import
Studienjahr:2021/2022