Lopsided Trees, I: Analyses

Autor: Vicky Choi, Mordecai J. Golin
Rok vydání: 2001
Předmět:
Zdroj: Algorithmica. 31:240-290
ISSN: 1432-0541
0178-4617
DOI: 10.1007/s00453-001-0063-1
Popis: Lopsided trees are rooted, ordered trees in which the length of an edge from a node to its i th child depends upon the value of i . These trees model a variety of problems and have therefore been extensively studied. In this paper we combine analytic and combinatorial techniques to address three open problems on such trees: 1. Given n , characterize the combinatorial structure of a lopsided tree with n leaves that has minimal external path length. 2. Express the cost of the minimal external path length tree as a function of n . 3. Calculate exactly how many nodes of depth ≤ x exist in the infinite lopsided tree.
Databáze: OpenAIRE
Externí odkaz: