๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

An optimal pram algorithm for a spanning tree on trapezoid graphs

โœ Scribed by Debashis Bera; Madhumangal Pal; Tapan K. Pal

Publisher
Springer-Verlag
Year
2003
Tongue
English
Weight
143 KB
Volume
12
Category
Article
ISSN
1598-5865

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

An optimal EREW PRAM algorithm for minim
An optimal EREW PRAM algorithm for minimum spanning tree verification
โœ Valerie King; Chung Keung Poon; Vijaya Ramachandran; Santanu Sinha ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 661 KB

We present a deterministic parallel algorithm on the EREW PRAM model to verify a minimum spanning tree of a graph. The algorithm runs on a graph with n vertices and m edges in O(logn) time and O(m + n) work. The algorithm is a parallelization of King's linear time sequential algorithm for the proble

A linear time algorithm for finding dept
A linear time algorithm for finding depth-first spanning trees on trapezoid graphs
โœ Hon-Chan Chen; Yue-Li Wang ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 458 KB

Let G be a connected graph of n vertices and m edges. The problem of finding a depth-first spanning tree of G is to find a subgraph of G connecting the n vertices with n -1 edges by depth-first search. In this paper, we propose an O(n) time algorithm for solving this problem on trapezoid graphs. Our