Abstract
We investigate methods for parallel algorithm design with emphasis on graph algorithms in this chapter. Shared memory and distributed memory parallel processing are the two fundamental models at hardware, operating system, programming, and algorithmic levels of parallel computation. We review these methods and describe static and dynamic load balancing in parallel computing systems.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Belloch G (2015) Algorithm design: parallel and sequential, Draft book
Flynn MJ (1972) Some computer organizations and their effectiveness. IEEE Trans. Comput. C21(9):948960
Foster I (1995) Designing and building parallel programs: concepts and tools for parallel software engineering. Addison-Wesley, Boston
Gantt HL (1910) Work, wages and profit, The engineering magazine, New York
Grama A, Karypis G, Kumar V, Gupta A (2003) Introduction to parallel computing, 2nd edn. Addison-Wesley, Boston
Karypis G, Kumar V (1995) Multilevel k-way partitioning scheme for irregular graphs. Technical Report TR 95-064, Department of Computer Science, University of Minnesota
Karypis G, Kumar V (1997) A coarse-grain parallel formulation of multilevel k-way graph partitioning algorithm. In: 8th SIAM conference on parallel processing for scientific computing
Kernighan BW, Lin S (1970) An efficient heuristic procedure for partitioning graphs. Bell Syst Tech J 49:291307
POSIX.1 FAQ. The open group, 5 Oct 2011
Quinn M (2003) Parallel programming in C with MPI and OpenMP, 1st edn. McGraw-Hill Science/Engineering/Math, New York
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG, part of Springer Nature
About this chapter
Cite this chapter
Erciyes, K. (2018). Parallel Graph Algorithms. In: Guide to Graph Algorithms. Texts in Computer Science. Springer, Cham. https://doi.org/10.1007/978-3-319-73235-0_4
Download citation
DOI: https://doi.org/10.1007/978-3-319-73235-0_4
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-73234-3
Online ISBN: 978-3-319-73235-0
eBook Packages: Computer ScienceComputer Science (R0)