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

An optimal algorithm for finding depth-first spanning tree on permutation graphs

โœ Scribed by Mondal, Sukumar ;Pal, Madhumangal ;Pal, Tapan K.

Publisher
Springer-Verlag
Year
1999
Tongue
English
Weight
103 KB
Volume
6
Category
Article
ISSN
1226-0061

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

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

An optimal EREW parallel algorithm for c
An optimal EREW parallel algorithm for computing breadth-first search trees on permutation graphs
โœ H.S. Chao; F.R. Hsu; R.C.T. Lee ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 498 KB

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