AN OPTIMAL EREW PARALLEL ALGORITHM FOR COMPUTING BREADTH-FIRST SEARCH-TREES ON PERMUTATION GRAPHS

Authors
CHAO HS HSU FR LEE RCT
Citation
Hs. Chao et al., AN OPTIMAL EREW PARALLEL ALGORITHM FOR COMPUTING BREADTH-FIRST SEARCH-TREES ON PERMUTATION GRAPHS, Information processing letters, 61(6), 1997, pp. 311-316
Citations number
5
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
61
Issue
6
Year of publication
1997
Pages
311 - 316
Database
ISI
SICI code
0020-0190(1997)61:6<311:AOEPAF>2.0.ZU;2-F
Abstract
Given a undirected graph G, the breadth-first search tree is construct ed by a breadth-first search on G. In this paper, an optimal parallel algorithm is presented for constructing the breadth-first search tree for permutation graphs in O(log n) time by using O(n/log n) processors under the EREW PRAM model, where n is the number of nodes of the grap h.