Skip to Main content Skip to Navigation
Conference papers

On the number of transversals in random trees

Abstract : 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.
Complete list of metadata

Cited literature [16 references]  Display  Hide  Download

https://hal.inria.fr/hal-01197246
Contributor : Coordination Episciences Iam <>
Submitted on : Friday, September 11, 2015 - 12:55:10 PM
Last modification on : Tuesday, November 24, 2020 - 1:30:03 PM
Long-term archiving on: : Tuesday, December 29, 2015 - 12:36:27 AM

File

dmAQ0112.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01197246, version 1

Collections

Citation

Bernhard Gittenberger, Veronika Kraus. On the number of transversals in random trees. 23rd International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'12), 2012, Montreal, Canada. pp.141-154. ⟨hal-01197246⟩

Share

Metrics

Record views

382

Files downloads

693