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

Fast RNC and NC algorithms for maximal path sets

โœ Scribed by Ryuhei Uehara; Zhi-Zhong Chen; Xin He

Book ID
104326344
Publisher
Elsevier Science
Year
1999
Tongue
English
Weight
659 KB
Volume
215
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

โœฆ Synopsis

We present two parallel algorithms for finding a maximal set of paths in a given undirected graph. One is randomized and runs in O(logn) expected time with O(n + m) processors on a CRCW PRAM. The other is deterministic and runs in O(log' n) time with 0(&n + m)/ log n) processors on an EREW PRAM. The results improve on the previous bests and can also be extended to digraphs. We then use the results to improve the time complexity of the best previous NC approximation algorithm for the shortest superstring problem.

๐Ÿ“œ SIMILAR VOLUMES

Efficient Sequential and Parallel Algori
Efficient Sequential and Parallel Algorithms for Maximal Bipartite Sets
โœ D. Pearson; V.V. Vazirani ๐Ÿ“‚ Article ๐Ÿ“… 1993 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 344 KB

A maximal bipartite set (MBS) in an undirected graph \(G=(V, E)\) is a maximal collection of vertices \(B \subseteq V\) whose induced subgraph is bipartite. In this paper we present efficient sequential (linear time) and parallel (NC) algorithms for constructing an MBS. 1.1993 Acatemic Press, Inc