A DATA-PARALLEL ALGORITHM FOR MINIMUM-WIDTH TREE LAYOUT

Authors
LANG W
Citation
W. Lang, A DATA-PARALLEL ALGORITHM FOR MINIMUM-WIDTH TREE LAYOUT, Information processing letters, 67(1), 1998, pp. 21-28
Citations number
9
Categorie Soggetti
Computer Science Information Systems","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
67
Issue
1
Year of publication
1998
Pages
21 - 28
Database
ISI
SICI code
0020-0190(1998)67:1<21:ADAFMT>2.0.ZU;2-7
Abstract
The tree-layout problem is to compute the coordinates of nodes of a tr ee so that the tree, when drawn on a piece of paper, appeals to human understanding. The tree-layout problem, which seems inherently sequent ial at the first glance, can be solved with a data-parallel algorithm. It takes O(height x log width) time on width processors when proper c ommunication links between processors are available, where height and width are the height and width of the tree, respectively. The layout c alculated by the algorithm has the minimum width. (C) 1998 Elsevier Sc ience B.V. All rights reserved.