Massively Parallel Algorithms for Geometric Graphs

Please enable javascript in your browser.

Jabbarzadeh Ganjeh, Peyman | 2021

652 Viewed

Type of Document: M.Sc. Thesis
Language: Farsi
Document No: 54708 (19)
University: Sharif University of Technology
Department: Computer Engineering
Advisor(s): Abam, Mohammad Ali
Abstract:
Geometric Spanner is a well-known problem aiming to add some edges between given points to build a graph in which the distance of each two nodes is at most their euclidean distance multiplied by t. One answer for this question can be the complete graph. But we like to use a smaller graph and minimize total edge weights, number of edges, or maximum degree of the graph. We study this problem in the Massively Parallel Computation model. In this model, each machine has not enough space to save all input data. We should divide input into multiple machines and run our algorithm in multiple steps. In each step, each machine computes with only a partition of data. After that, machines share their output. Then, they start the next step with the new data from other machines. Given that communication between machines takes a long time, the goal is to minimize the number of steps. We solve Geometric Spanner with machines that have O(√n) space using only constant steps
Keywords:
Geometric Graphs ; T-Spanner Problem ; Massively Parallel Computation