License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.AofA.2020.5
URN: urn:nbn:de:0030-drops-120352
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12035/
Berzunza, Gabriel ;
Cai, Xing Shi ;
Holmgren, Cecilia
The k-Cut Model in Conditioned Galton-Watson Trees
Abstract
The k-cut number of rooted graphs was introduced by Cai et al. [Cai and Holmgren, 2019] as a generalization of the classical cutting model by Meir and Moon [Meir and Moon, 1970]. In this paper, we show that all moments of the k-cut number of conditioned Galton-Watson trees converge after proper rescaling, which implies convergence in distribution to the same limit law regardless of the offspring distribution of the trees. This extends the result of Janson [Janson, 2006].
BibTeX - Entry
@InProceedings{berzunza_et_al:LIPIcs:2020:12035,
author = {Gabriel Berzunza and Xing Shi Cai and Cecilia Holmgren},
title = {{The k-Cut Model in Conditioned Galton-Watson Trees}},
booktitle = {31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
pages = {5:1--5:10},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-147-4},
ISSN = {1868-8969},
year = {2020},
volume = {159},
editor = {Michael Drmota and Clemens Heuberger},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12035},
URN = {urn:nbn:de:0030-drops-120352},
doi = {10.4230/LIPIcs.AofA.2020.5},
annote = {Keywords: k-cut, cutting, conditioned Galton-Watson trees}
}
|
Keywords: |
|
k-cut, cutting, conditioned Galton-Watson trees |
|
Collection: |
|
31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
10.06.2020 |
