Bernhard Gittenberger ; Veronika Kraus - On the number of transversals in random trees

dmtcs:2990 - Discrete Mathematics & Theoretical Computer Science, January 1, 2012, DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12) - https://doi.org/10.46298/dmtcs.2990
On the number of transversals in random trees

Authors: Bernhard Gittenberger ; Veronika Kraus

    We study transversals in random trees with n vertices asymptotically as n tends to infinity. Our investigation treats the average number of transversals of fixed size, the size of a random transversal as well as the probability that a random subset of the vertex set of a tree is a transversal for the class of simply generated trees and for Pólya trees. The last parameter was already studied by Devroye for simply generated trees. We offer an alternative proof based on generating functions and singularity analysis and extend the result to Pólya trees.


    Volume: DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12)
    Section: Proceedings
    Published on: January 1, 2012
    Imported on: January 31, 2017
    Keywords: simply generated trees,Pólya trees,singularity analysis,functional equations,[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG]
    Fundings :
      Source : OpenAIRE Research Graph
    • Information Measures to Characterize Networks; Funder: Austrian Science Fund (FWF); Code: P 22029

    Share

    Consultation statistics

    This page has been seen 165 times.
    This article's PDF has been downloaded 308 times.