TY - JOUR

T1 - A data-parallel algorithm for minimum-width tree layout

AU - Yang, Wuu

PY - 1998/7/16

Y1 - 1998/7/16

N2 - The tree-layout problem is to compute the coordinates of nodes of a tree so that the tree, when drawn on a piece of paper, appeals to human understanding. The tree-layout problem, which seems inherently sequential at the first glance, can be solved with a data-parallel algorithm. It takes O(height × log width) time on width processors when proper communication links between processors are available, where height and width are the height and width of the tree, respectively. The layout calculated by the algorithm has the minimum width.

AB - The tree-layout problem is to compute the coordinates of nodes of a tree so that the tree, when drawn on a piece of paper, appeals to human understanding. The tree-layout problem, which seems inherently sequential at the first glance, can be solved with a data-parallel algorithm. It takes O(height × log width) time on width processors when proper communication links between processors are available, where height and width are the height and width of the tree, respectively. The layout calculated by the algorithm has the minimum width.

KW - Algorithms

KW - Data-parallel algorithms

KW - EREW

KW - PRAM

KW - Tree layout

UR - http://www.scopus.com/inward/record.url?scp=0042353948&partnerID=8YFLogxK

U2 - 10.1016/S0020-0190(98)00081-7

DO - 10.1016/S0020-0190(98)00081-7

M3 - Article

AN - SCOPUS:0042353948

VL - 67

SP - 21

EP - 28

JO - Information Processing Letters

JF - Information Processing Letters

SN - 0020-0190

IS - 1

ER -