IIIT Hyderabad Publications 


Applications of Ear Decomposition to Efficient Heterogeneous Algorithms for Shortest Path/Cycle ProblemAuthor: Debarshi Dutta Date: 20180716 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 AllPairsShortestPaths (\apsp), MinimumCycleBasis(\cb) and related problems. Indeed there are several efficient implementations for such problems on a variety of modern multi and manycore architectures. It can be noticed that for several graph problems, parallelism offers only a limited success as current parallel architectures have severe shortcomings 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 shortestpaths and minimumcostcyclebasis. An ear decomposition of a graph $G$ is a partition of the edge set of $G$ into a sequence of edgedisjoint 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 AllPairs Shortest Path and Minimum Cycle Basis problems. Full thesis: pdf Centre for Security, Theory and Algorithms 

Copyright © 2009  IIIT Hyderabad. All Rights Reserved. 