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.2346
Some simple varieties of trees arising in permutation analysis

Authors: Mathilde Bouvel 1; Marni Mishna 2; Cyril Nicaud 3

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.

https://doi.org/10.46298/dmtcs.2346
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

Linked publications - datasets - softwares

Source : ScholeXplorer IsRelatedTo DOI 10.1016/s0022-0000(76)80045-1
  • 10.1016/s0022-0000(76)80045-1
Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms

Share and export

Consultation statistics

This page has been seen 198 times.
This article's PDF has been downloaded 334 times.