Abstract
dc:description.abstractLarge sizes of real-world data graphs, such as social networks, communication networks, hyperlink networks, and model-checking networks, call for fast and scalable analytic algorithms. The shared-memory multicore machine is a prevalent parallel computation model that can handle such volumes of data. Unfortunately, many graph algorithms do not take full advantage of such a parallel model. This thesis focuses on the parallelism of two graph problems, graph trimming and core maintenance. Graph trimming is to prune the vertices without outgoing edges; core maintenance is to maintain the core numbers of vertices when inserting or removing edges, where the core number of a vertex can be a parameter of density in the graph. The goal of this thesis is to develop fast, provable, and scalable parallel graph algorithms that perform on shared-memory multicore machines. Toward this goal, we first discuss the sequential algorithms and then propose corresponding parallel algorithms. The thesis adopts a three-pronged approach of studying parallel graph algorithms from the algorithm design, correctness proof, and performance analysis. Our experiments on multicore machines show significant speedups over various real and synthetic graphs.
Degree
thesis:*- Department dc:contributor.department
- Computing and Software
- Year dc:date.issued
- 2023
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- GUO, BIN
- Advisor dc:contributor.advisor
-
- Emil, Sekerinski
Subjects
dc:subject × 5Rights
- Language dc:language.iso
- en
Identifiers
dc:identifier.*- Identifier URI
- https://doi.org/10.71548/10053