COMP 5704: Parallel Algorithms and Applications in Data Science

School of Computer Science Carleton University, Ottawa, Canada

---

Project Title: Dynamic Massive Parallel Computation Model for Graph Problems

Name: Isabelle Liu

E-Mail: isabelleliu@cmail.carleton.ca

---

Project Outline: In this project, I aim to implement and test the dynamic algorithm in the Dynamic Massive Parallel Computation (DMPC) model by Italiano et al. on an alternative graph-theoretic problem, the maximal independent set.

Startup Paper(s): Dynamic Algorithms for the Massively Parallel Computation Model

Deliverables:

• Literature Review (PDF file created from LATEX template)
• Presentation Outline (PDF file created from LATEX template)
• Slide Presentation (PowerPoint File) incl. Question Sheet
• Final Paper (PDF file created from LATEX template)
• Code and Data (put all code, data, etc. into this directory)

Relevant References:

• Parallel Graph Connectivity in Log Diameter Rounds
• Fully Dynamic Maximal Independent Set with Sublinear Update Time
• Fully Dynamic Maximal Independent Set with Sublinear in n Update Time
• Massively Parallel Dynamic Programming on Trees
• Massively Parallel Computation via Remote Memory Access
• Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time
• Optimal Dynamic Distributed MIS
• Parallel Batch-Dynamic Graphs: Algorithms and Lower Bounds
• Massively Parallel Architectures for AI: NETL, Thistle, and Boltzmann Machines
• Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover
• Sparsifying Distributed Algorithms with Ramifications in Massively Parallel Computation and Centralized Local Computation
• A Model of Computation for MapReduce
• Shuffles and Circuits: (On Lower Bounds for Modern Parallel Computation)
• Massively Parallel Algorithms and Hardness for Single-Linkage Clustering under l_p Distances