Fast RNC and NC algorithms for maximal path sets

We present two parallel algorithms for finding a maximal set of paths in a given undirected graph. One is randomized and runs in O(log n) expected tim e with O(n + m) processors on a CRCW PRAM. The other is deterministic and r uns in O(log(2) n) time with O(Delta(2)(n + m)/ log n) processors on an ERE W 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 probl em. (C) 1999-Elsevier Science B.V. All rights reserved