Embedding small digraphs and permutations in binary trees and split trees

DOI10.1007/s00453-019-00667-5zbMath1444.05120OpenAlexW3003200373MaRDI QIDQ2292861

Cecilia Holmgren, Tony Johansson, Fiona Skerman, Michael Henry Albert

Publication date: 6 February 2020

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-019-00667-5

zbMATH Keywords

permutationscumulantsrandom treesinversionssplit trees

Mathematics Subject Classification ID

Trees (05C05) Exact enumeration problems, generating functions (05A15) Permutations, words, matrices (05A05) Enumeration in graph theory (05C30) Combinatorial probability (60C05) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Directed graphs (digraphs), tournaments (05C20) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (3)

Tree limits and limits of random trees ⋮ Inversions in Split Trees and Conditional Galton–Watson Trees ⋮ Split trees -- a unifying model for many important random trees of logarithmic height: a brief survey

Uses Software

• Quicksort

Cites Work

• Unnamed Item
• Novel characteristics of split trees by use of renewal theory
• Runs in labelled trees and mappings
• On the analysis of linear probing hashing
• Quad trees: A data structure for retrieval by composite keys
• Rooted forests that avoid sets of permutations
• Limiting distributions for the number of inversions in labelled tree families
• Universal Limit Laws for Depths in Random Trees
• Enumeration of trees by inversions
• Embedding small digraphs and permutations in binary trees and split trees
• Inversions in Split Trees and Conditional Galton–Watson Trees
• The inversion enumerator for labeled trees
• Quicksort
• Enumerating alternating trees
• Generalized parking functions, tree inversions, and multicolored graphs

This page was built for publication: Embedding small digraphs and permutations in binary trees and split trees