Nothing Special   »   [go: up one dir, main page]
Skip to main content
SpringerLink
Log in

Fast RNC and NC algorithms for finding a maximal set of paths with an application

  • Session 6
  • Conference paper
  • First Online:
Computing and Combinatorics (COCOON 1996)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 1090))

Included in the following conference series:

  • 157 Accesses

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 \(\frac{1}{{3 + \varepsilon }}\)for any ε >0.

For a full version, contact chen@r.dendai.ac.jp.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Z.-Z. Chen, A fast and efficient NC algorithm for maximal matching, Inform. Process. Lett. 55 (1995) 303–307.

    Google Scholar 

  2. Z.-Z. Chen, NC algorithms for finding a maximal set of paths with application to compressing strings, in: Proc. 22nd International Colloquium on Automata, Languages, and Programming, Lecture Notes in Computer Science, Vol. 944 (Springer, Berlin, 1995), 99–110; journal version to appear in Theoretical Computer Science.

    Google Scholar 

  3. A. Israeli and A. Itai, A fast and simple randomized parallel algorithm for maximal matching, Inform. Process, Lett. 22 (1986) 77–80.

    Google Scholar 

  4. T. Jiang, M. Li, and D.-z. Du, A note on shortest superstrings with flipping, Inform. Process. Lett. 44 (1992) 195–199.

    Google Scholar 

  5. D.C. Kozen, The Design and Analysis of Algorithms (Springer, New York, 1992).

    Google Scholar 

  6. R. Motwani and P. Raghavan, Randomized Algorithms (Cambridge University Press, 1995).

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Center for Inform. Sci., Tokyo Woman's Christian Univ., Suginami, 167, Tokyo

    Ryuhei Uehara

  2. Dept. of Math. Sci., Tokyo Denki Univ., Hatoyama, 350-03, Saitama, Japan

    Zhi-Zhong Chen

  3. Dept. of Comput. Sci., SUNY at Buffalo, 14260, Buffalo, NY, USA

    Xin He

Authors
  1. Ryuhei Uehara
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Zhi-Zhong Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Xin He
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Jin-Yi Cai Chak Kuen Wong

Rights and permissions

Reprints and permissions

Copyright information

© 1996 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Uehara, R., Chen, ZZ., He, X. (1996). Fast RNC and NC algorithms for finding a maximal set of paths with an application. In: Cai, JY., Wong, C.K. (eds) Computing and Combinatorics. COCOON 1996. Lecture Notes in Computer Science, vol 1090. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-61332-3_154

Download citation

  • DOI: https://doi.org/10.1007/3-540-61332-3_154

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-61332-9

  • Online ISBN: 978-3-540-68461-9

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation