A COST-OPTIMAL EREW BREADTH-FIRST ALGORITHM FOR ORDERED TREES, WITH APPLICATIONS*
作者:
RONG LIN,
STEPHAN OLARIU,
期刊:
Parallel Algorithms and Applications
(Taylor Available online 1995)
卷期:
Volume 5,
issue 3-4
页码: 187-197
ISSN:1063-7192
年代: 1995
DOI:10.1080/10637199508915484
出版商: Taylor & Francis Group
关键词: Ordered trees;binary trees;encodings;traversals;Breadth-First search;encoding;parallel algorithms;EREW-PRAM
数据来源: Taylor
摘要:
Encoding the shape of a tree is a basic step in a number of algorithms in integrated circuit design, automated theorem proving, and game playing. We propose a simple cost-optimal encoding algorithm for ordered trees and show that our encoding can be used to obtain an optimal Breadth-First traversal of ordered trees. Specifically, with an n-node ordered tree as input our algorithms run in O(logn) time using O(n/logn) processors in the EREW-PRAM model of computation. We then show that the Breadth-First algorithm can be used to produce new encodings of binary and ordered trees.
点击下载:
PDF (191KB)
返 回