✦ LIBER ✦

An optimal EREW parallel algorithm for computing breadth-first search trees on permutation graphs

✍ Scribed by H.S. Chao; F.R. Hsu; R.C.T. Lee

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 498 KB
Volume: 61
Category: Article
ISSN: 0020-0190
DOI: 10.1016/s0020-0190(97)00009-4

No coin nor oath required. For personal study only.

✦ Synopsis

Given a undirected graph G, the breadth-first search tree is constructed 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/Iog n) processors under the EREW PRAM model, where n is the number of nodes of the graph.

📜 SIMILAR VOLUMES

Efficient algorithms for finding depth-f

Efficient algorithms for finding depth-first and breadth-first search trees in permutation graphs

✍ C. Rhee; Y.Daniel Liang; S.K. Dhall; S. Lakshmivarahan 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 512 KB

An O(log n) parallel algorithm for const

An O(log n) parallel algorithm for constructing a spanning tree on permutation graphs

✍ Wang Yue-Li; Chen Hon-Chan; Lee Chen-Yu 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 396 KB