 |
Discrete Mathematics & Theoretical Computer Science |
Mathilde Bouvel ; Marni Mishna ; Cyril Nicaud - Some simple varieties of trees arising in permutation analysis
dmtcs:2346 - Discrete Mathematics & Theoretical Computer Science, January 1, 2013, DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013) - https://doi.org/10.46298/dmtcs.2346Some simple varieties of trees arising in permutation analysisArticle
Authors: Mathilde Bouvel 1; Marni Mishna 2; Cyril Nicaud 
3
- 1 Laboratoire Bordelais de Recherche en Informatique
- 2 Department of Mathematics [Burnaby]
- 3 Laboratoire d'Informatique Gaspard-Monge
After extending classical results on simple varieties of trees to trees counted by their number of leaves, we describe a filtration of the set of permutations based on their strong interval trees. For each subclass we provide asymptotic formulas for number of trees (by leaves), average number of nodes of fixed arity, average subtree size sum, and average number of internal nodes. The filtration is motivated by genome comparison of related species.
Source: HAL:hal-01229665v1
Volume: DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013)
Section: Proceedings
Published on: January 1, 2013
Imported on: November 21, 2016
Keywords: permutations,simple varieties of trees,random generation,tree parameters,asymptotic formulas,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]
Funding:
- Source : OpenAIRE Graph
- Funder: Natural Sciences and Engineering Research Council of Canada
Consultation statistics
This page has been seen 356 times.
This article's PDF has been downloaded 430 times.