We study fundamental graph problems under parallel computing models. In particular, we consider two parallel computing models: Parallel Random Access Machine (PRAM) and Massively Parallel Computation (MPC). The PRAM model is a classic model of parallel computation. The efficiency of a PRAM algorithm is measured by its parallel time and the number of processors needed to achieve the parallel time. The MPC model is an abstraction of modern massive parallel computing systems such as MapReduce, Hadoop and Spark. The MPC model captures well coarse-grained computation on large data --- data is distributed to processors, each of which has a sublinear (in the input data) amount of local memory and we alternate between rounds of computation and rounds of communication, where each machine can communicate an amount of data as large as the size of its memory. We usually desire fully scalable MPC algorithms, i.e., algorithms that can work for any local memory size. The efficiency of a fully scalable MPC algorithm is measured by its parallel time and the total space usage (the local memory size times the number of machines).
Consider an π-vertex π-edge undirected graph πΊ (either weighted or unweighted) with diameter π· (the largest diameter of its connected components). Let π=π+π denote the size of πΊ. We present a series of efficient (randomized) parallel graph algorithms with theoretical guarantees. Several results are listed as follows:
1) Fully scalable MPC algorithms for graph connectivity and spanning forest using π(π) total space and π(log π·loglog_{π/π} π) parallel time.
2) Fully scalable MPC algorithms for 2-edge and 2-vertex connectivity using π(π) total space where 2-edge connectivity algorithm needs π(log π·loglog_{π/π} π) parallel time, and 2-vertex connectivity algorithm needs π(log π·βΈ±logΒ²log_{π/π} n+\log D'βΈ±loglog_{π/π} π) parallel time. Here π·' denotes the bi-diameter of πΊ.
3) PRAM algorithms for graph connectivity and spanning forest using π(π) processors and π(log π·loglog_{π/π} π) parallel time.
4) PRAM algorithms for (1 + π)-approximate shortest path and (1 + π)-approximate uncapacitated minimum cost flow using π(π) processors and poly(log π) parallel time.
These algorithms are built on a series of new graph algorithmic primitives which may be of independent interests.
| Identifer | oai:union.ndltd.org:columbia.edu/oai:academiccommons.columbia.edu:10.7916/d8-pnyz-ck91 |
| Date | January 2021 |
| Creators | Zhong, Peilin |
| Source Sets | Columbia University |
| Language | English |
| Detected Language | English |
| Type | Theses |
Page generated in 0.002 seconds