Parallel Graph Algorithms III
Embedded Files
::: Home > Instruction > CMSC 280: Parallel Processing > Topic 06: Parallel Graph Algorithms III
This final graph algorithms topic explores methods for determining connectivity and coloring, which are crucial for scheduling and resource allocation problems. Students will study parallel approaches for finding connected components using search techniques and label propagation, and examine the challenges of distributed graph coloring, which often relies on iterative refinement and conflict resolution.
Learning Outcomes
Learning Outcomes
The parallel computation of connected components is understood, and the communication and convergence behavior of label-propagation and pointer-jumping techniques are analyzed.
The strategies for achieving fault tolerance in large-scale distributed graph processing systems are described, emphasizing localized recovery and scalability.
The formulation and application of parallel graph coloring algorithms are examined, with attention to conflict resolution, iterative refinement, and real-world applications in scheduling and register allocation.
Topic Outline
Topic Outline
Handout: Parallel Graph Algorithms III*
When Structure Must Endure
Graph Connectivity Problems
Parallel Connected Components: Label Propagation
Resilience in Graph Processing: Fault Tolerance
Parallel Graph Coloring
Distributed Coloring: Conflict Resolution
Applications: Scheduling and Register Allocation
From Structure to Search
Note: Links marked with an asterisk (*) lead to materials accessible only to members of the University community. Please log in with your official University account to view them.
Readings
Readings
Parallel Connected Components (Shiloach-Vishkin)
Shiloach, Y., & Vishkin, U. (1982). An O(log n) parallel connectivity algorithm. Journal of Algorithms, 3(1), 57–67.
Parallel Graph Coloring and Maximal Independent Set (Luby's Algorithm)
Luby, M. (1986). A fast parallel algorithm for the maximal independent set problem. SIAM Journal on Computing, 15(4), 1036–1053.
Large-Scale Graph Processing Systems (Fault Tolerance and Implementation)
Malewicz, G., Austern, M. H., Bik, A. J. C., Dehnert, J. C., Horn, I., Leiser, N., & Czajkowski, P. (2010). Pregel: A system for large-scale graph processing. Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data, 135–146.
Access Note: Published research articles and books are linked to their respective sources. Some materials are freely accessible within the University network or when logged in with official University credentials. Others will be provided to enrolled students through the class learning management system (LMS).
::: Home > Instruction > CMSC 280: Parallel Processing > Topic 06: Parallel Graph Algorithms III
Page updated
Report abuse