Isolating a Leaf in Rooted Trees via Random Cuttings |
| |
Authors: | Markus Kuba Alois Panholzer |
| |
Institution: | 1. Institut für Diskrete Mathematik und Geometrie, Technische Universit?t Wien, Wiedner Hauptstr. 8-10/104, 1040, Wien, Austria
|
| |
Abstract: | We consider a recursive procedure for destroying rooted trees and isolating a leaf by removing a random edge and keeping the
subtree, which does not contain the original root. For two tree families, the simply generated tree families and increasing
tree families, we study here the number of random cuts that are necessary to isolate a leaf. We can show limiting distribution
results of this parameter for simply generated trees and certain increasing trees.
This work was supported by the Austrian Science Foundation FWF, grant S9608-N13. |
| |
Keywords: | :" target="_blank">: simply generated trees recursive trees cutting-down procedure node isolation limiting distribution |
本文献已被 SpringerLink 等数据库收录! |
|