PARALLEL TREE-CONTRACTION AND FIBONACCI NUMBERS

Authors
PLANDOWSKI W RYTTER W SZYMACHA T
Citation
W. Plandowski et al., PARALLEL TREE-CONTRACTION AND FIBONACCI NUMBERS, Information processing letters, 59(5), 1996, pp. 267-271
Citations number
8
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
59
Issue
5
Year of publication
1996
Pages
267 - 271
Database
ISI
SICI code
0020-0190(1996)59:5<267:PTAFN>2.0.ZU;2-X
Abstract
We show a new property of Fibonacci numbers which is related to the an alysis of a very simple and natural parallel tree contraction algorith m. We show that the size of the smallest tree which requires t contrac tions equals exactly the tth Fibonacci number. This implies the sharp bound on the number of iterations of the tree contraction algorithm. W e contribute also to combinatorics of trees.