ROUTING ON TREES

Authors
SYMVONIS A
Citation
A. Symvonis, ROUTING ON TREES, Information processing letters, 57(4), 1996, pp. 215-223
Citations number
6
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
57
Issue
4
Year of publication
1996
Pages
215 - 223
Database
ISI
SICI code
0020-0190(1996)57:4<215:ROT>2.0.ZU;2-5
Abstract
In this paper, we study the permutation packet routing problem on tree s. We show that every permutation can be routed on a tree of n vertice s in n - 1 routing steps. We provide two algorithms that produce such routing schedules. The first algorithm builds in O(n(2)) time a schedu le that needs O(n(2)) bits for its description while the second one pr oduces in O(n(3)) time a schedule that can be described with O(n log n ) bits.