IIIT Hyderabad Publications |
|||||||||
|
Applications of Ear Decomposition to Efficient Heterogeneous Algorithms for Shortest Path/Cycle ProblemAuthor: Debarshi Dutta Date: 2018-07-16 Report no: IIIT/TH/2018/40 Advisor:Kishore Kothapalli AbstractGraph algorithms play an important role in several fields of sciences and engineering. Prominent among them are the All-Pairs-Shortest-Paths (\apsp), Minimum-Cycle-Basis(\cb) and related problems. Indeed there are several efficient implementations for such problems on a variety of modern multi- and many-core architectures. It can be noticed that for several graph problems, parallelism offers only a limited success as current parallel architectures have severe short-comings when deployed for most graph algorithms. At the same time, some of these graphs exhibit clear structural properties due to their sparsity. This calls for particular solution strategies aimed at scalable processing of large, sparse graphs on modern parallel architectures. In this thesis, we study the applicability of an ear decomposition of graphs to problems such as allpairs- shortest-paths and minimum-cost-cycle-basis. An ear decomposition of a graph $G$ is a partition of the edge set of $G$ into a sequence of edge-disjoint paths, such that only the end vertices of each path appear in earlier paths. We design and implement a new algorithm to obtain an ear decomposition for a biconnected graph, whose running time in practice is at least 2 times faster than Schmidt’s algorithm (state of the art). The speedup increases as the graph get denser. Through experimentation, we show that the resulting solutions are scalable in terms of both memory usage and also their speedup over best known current implementations. We believe that our techniques have the potential to be relevant for designing scalable solutions for other computations on large sparse graphs. We apply our proposed techniques on Graph Algorithms such as All-Pairs Shortest Path and Minimum Cycle Basis problems. Full thesis: pdf Centre for Security, Theory and Algorithms |
||||||||
Copyright © 2009 - IIIT Hyderabad. All Rights Reserved. |