@inproceedings{763108cda3c147f8ad0688f2fe463e2a,
title = "Fast RNC and NC algorithms for finding a maximal set of paths with an application",
abstract = "We present two parallel algorithms for finding a maximal set of paths in a given undirected graph. The former runs in O(log n) expected time with O(n + m) processors on a CRCW PRAM. The latter runs in O(log2 n) time with O(Δ2(n + m)/log n) processors on an EREW PRAM. The results improve on the best previous ones and can also be extended to digraphs. We then use the results to design an NC approximation algorithm for a variation of the shortest superstring problem introduced by Jiang et al. The approximation algorithm achieves a compression ratio of 1/3+εfor any ε >0.",
author = "Ryuhei Uehara and Chen, \{Zhi Zhong\} and Xin He",
note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1996.; 2nd Annual International Conference on Computing and Combinatorics, COCOON 1996 ; Conference date: 17-06-1996 Through 19-06-1996",
year = "1996",
doi = "10.1007/3-540-61332-3\_154",
language = "English",
isbn = "9783540613329",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "209--218",
editor = "Jin-Yi Cai and Wong, \{Chak Kuen\}",
booktitle = "Computing and Combinatorics - 2nd Annual International Conference, COCOON 1996, Proceedings",
address = "Germany",
}