Fast RNC and NC algorithms for maximal path sets

AbstractWe 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 time with O(n + m) processors on a CRCW PRAM. The other is deterministic and runs in O(log2 n) time with O(Δ2(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