A data-parallel algorithm for minimum-width tree layout

Wuu Yang*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish
Pages (from-to)21-28
Number of pages8
JournalInformation Processing Letters
Volume67
Issue number1
DOIs
StatePublished - 16 Jul 1998

Keywords

  • Algorithms
  • Data-parallel algorithms
  • EREW
  • PRAM
  • Tree layout

Fingerprint Dive into the research topics of 'A data-parallel algorithm for minimum-width tree layout'. Together they form a unique fingerprint.

Cite this