Parallel constructions of maximal path sets and applications to short superstrings

AbstractIt is shown that the problem of finding a maximal set of paths in a given (undirected or directed) graph is in NC. This result is then used to obtain three parallel approximation algorithms for the shortest superstring problem. The first is an NC algorithm achieving a compression ratio of 13 + ε for any ε > 0. The second is an RNC algorithm achieving a compression ratio of 3863 ≈ 0.603. The third is an RNC algorithm achieving an approximation ratio of 25063 ≈ 2.793. All the results significantly improve on the best previous ones