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 treesArticle

Authors: Bernhard Gittenberger 1; Veronika Kraus 2

  • 1 Institut für Diskrete Mathematik und Geometrie [Wien]
  • 2 Institute of Bioinformatics and Translational Research [UMIT]

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]
Funding:
    Source : OpenAIRE Graph
  • Information Measures to Characterize Networks; Funder: Austrian Science Fund (FWF); Code: P 22029

Consultation statistics

This page has been seen 203 times.
This article's PDF has been downloaded 344 times.