Parallel algorithms for linked list and beyond | SpringerLink
Skip to main content
Springer Nature Link
Log in

Parallel algorithms for linked list and beyond

  • Conference paper
  • First Online:
Algorithms (SIGAL 1990)

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

Included in the following conference series:

  • 247 Accesses

Abstract

Linked list problems are fundamental problems in the design of parallel algorithms. We present design techniques for linked list algorithms and applications of these algorithms.

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. R. J. Anderson, G. L. Miller. Optimal parallel algorithms for the list ranking problem, USC-Tech. Rept. 1986.

    Google Scholar 

  2. R. J. Anderson, G. L. Miller. Deterministic parallel list ranking. LNCS 319 (J. H. Reif ed.), 81–90.

    Google Scholar 

  3. R. A. Borodin and J. E. Hopcroft. Routing, merging and sorting on parallel models of computation. Proc. 14th ACM Symposium on Theory of Computing, 206–219 (1986).

    Google Scholar 

  4. B. S. Chlebus, K. Diks, T. Hagerup, T. Radzik. New simulations between CRCW PRAMs. LNCS 380, 95–104.

    Google Scholar 

  5. R. Cole and U. Vishkin. Approximate and exact parallel scheduling with applications to list, tree and graph problems, Proc. 27th Symp. on Foundations of Comput. Sci., IEEE, 478–491 (1986).

    Google Scholar 

  6. A. V. Goldberg, S. A. Plotkin, G. E. Shannon. Parallel symmetry-breaking in sparse graphs, SIAM J. on Discrete Math., Vol. 1, No. 4, 447–471 (Nov., 1988).

    Article  Google Scholar 

  7. Y. Han. Designing fast and efficient parallel algorithms. Ph.D. Thesis, Duke University, Durham, NC 27706, 1987.

    Google Scholar 

  8. Y. Han. Parallel algorithms for computing linked list prefix. J. of Parallel and Distributed Computing 6, 537–557 (1989).

    Article  Google Scholar 

  9. Y. Han. Matching partition a linked list and its optimization. Proc. ACM Symp. on Parallel Algorithms and Architectures, Sante Fe, New Mexico, 246–253 (1989).

    Google Scholar 

  10. Y. Han. An optimal linked list prefix algorithm on a local memory computer. Proc. 1989 ACM Computer Science Conf., Lousville, Kentucky, 278–286 (1989).

    Google Scholar 

  11. Y. Han. On the chromatic number of Shuffle graphs. TR. No. 140-89, Department of Computer Science, University of Kentucky, Lexington, KY 40506, USA.

    Google Scholar 

  12. H. Jung, K. Mehlhorn. Parallel algorithms for computing maximal independent sets in trees and for updating minimum spanning trees, Information Processing Letters, Vol. 27, No. 5, 227–236 (1988).

    Google Scholar 

  13. N. C. Kalra, P. C. P. Bhatt. Parallel algorithms for tree traversals, Parallel Computing, Vol. 2, No. 2, June 1985.

    Google Scholar 

  14. C. P. Kruskal, T. Madej, L. Rudolph. Parallel prefix on fully connected direct connection machine. Proc. 1986 Int. Conf. on Parallel Processing, 278–284.

    Google Scholar 

  15. C. P. Kruskal, L. Rudolph and M. Snir. Efficient parallel algorithms for graph problems. Proc. 1986 International Conf. on Parallel Processing, 869–876.

    Google Scholar 

  16. N. Linial. Distributive graph algorithms — global solutions from local data. Proc. 1987 IEEE Symposium on Foundations of Computer Science, 331–336 (1987).

    Google Scholar 

  17. G. L. Miller, J. H. Reif. Parallel tree contraction and its application. Proc. 1985 IEEE Foundations of Computer Science, 478–489.

    Google Scholar 

  18. I. Parberry. On the time required to sum n semigroup elements on a parallel machine with simultaneous writes. LNCS, 227, 296–304.

    Google Scholar 

  19. J. H. Reif. An optimal parallel algorithm for integer sorting, Proc. 26th Symp. on Foundations of Computer Sci., IEEE, 291–298 (1985).

    Google Scholar 

  20. K. W. Ryu, J. JáJá. List ranking on the hypercube. Proc. 1989 Int. Conf. on Parallel Processing. St. Charles, Illinois, (Aug. 1989).

    Google Scholar 

  21. M. Snir. On parallel searching. SIAM J. Comput, Vol. 14, No. 3, 688–708 (Aug., 1985).

    Article  Google Scholar 

  22. E. Sperner. Ein satz über untermenger endlichen menge, Math. Z. 27 (1928), 544–548.

    Article  Google Scholar 

  23. R. E. Tarjan, U. Vishkin. Finding biconnected components and computing tree functions in logarithmic time, 25th Symp. on Foundations of Computer Sci., IEEE, 12–20.

    Google Scholar 

  24. J. D. Ullman. Computational aspects of VLSI, Computer Science Press, 1984.

    Google Scholar 

  25. R. A. Wagner, Y. Han. Parallel algorithms for bucket sorting the data dependent prefix problem. Proc. 1986 Int. Conf. on Parallel Processing, 924–930.

    Google Scholar 

  26. J. C. Wyllie. The complexity of parallel computation. TR 79-387, Department of Computer Science, Cornell University, Ithaca, NY, 1979.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, University of Kentucky, 40506, Lexington, KY, USA

    Yijie Han

Authors
  1. Yijie Han
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Tetsuo Asano Toshihide Ibaraki Hiroshi Imai Takao Nishizeki

Rights and permissions

Reprints and permissions

Copyright information

© 1990 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Han, Y. (1990). Parallel algorithms for linked list and beyond. In: Asano, T., Ibaraki, T., Imai, H., Nishizeki, T. (eds) Algorithms. SIGAL 1990. Lecture Notes in Computer Science, vol 450. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-52921-7_58

Download citation

  • DOI: https://doi.org/10.1007/3-540-52921-7_58

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-52921-7

  • Online ISBN: 978-3-540-47177-6

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation