IIIT Hyderabad Publications |
|||||||||
|
Graph Decomposition Techniques for Parallel Symmetry BreakingAuthor: Sayyad Nayyaroddeen Date: 2019-02-05 Report no: IIIT/TH/2019/19 Advisor:Kishore Kothapalli AbstractParallel algorithms on large graphs play a key role in various problems from several domains of sciences and engineering. Of these, symmetry breaking problems such as matchings and colorings are fundamental owing to a large number of applications. Algorithms for symmetry breaking problems are studied in several parallel/distributed settings over the decades. However, as the size of graphs corresponding to real-world phenomenon increase, it is imperative to use not only just parallelism but also algorithmic enhancements based on the structure of real-world graphs. A popular approach in this context is to use a graph decomposition to break the problem into multiple subproblems the solutions of which can be used to solve the original problem. A big question in this direction that is left unanswered by current research is to study which decomposition is appropriate for a given computation and a target architecture. In this context, we address the above question with respect to four problems: Maximal Matching (MM), Vertex Coloring (COLOR), Balanced Coloring (BCOL), and Approximate Weighted Matching (AWM). For these four problems, we study four different decomposition techniques including one based on bridges, one based on a random partitioning, one based on vertices of degree k for a given k, and the popular METIS based decomposition. We show that existing algorithms for the above computations on a multi-core CPU and a GPU can be significantly improved by making use of an appropriate decompo- sition of the input graph. Our study indicates that the exact decomposition to use depends both on the problem and the target architecture. Full thesis: pdf Centre for Security, Theory and Algorithms |
||||||||
Copyright © 2009 - IIIT Hyderabad. All Rights Reserved. |