文章基本信息

标题：Applications of Ear Decomposition to Efficient Heterogeneous Algorithms for Shortest Path/Cycle Problems
其他标题：Applications of Ear Decomposition to Efficient Heterogeneous Algorithms for Shortest Path/Cycle Problems
本地全文：下载
作者：Debarshi Dutta ; Meher Chaitanya ; Kishore Kothapalli 等
期刊名称：International Journal of Networking and Computing
印刷版ISSN：2185-2847
出版年度：2018
卷号：8
期号：1
页码：73-92
语种：English
出版社：International Journal of Networking and Computing
摘要：Graph algorithms play an important role in several fields of sciences and engineering. Prominent among them are the All-Pairs-Shortest-Paths (APSP) 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 paper, we study the applicability of an ear decomposition of graphs to problems such as all-pairs-shortest-paths and minimum cost cycle basis. 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.
其他摘要：Graph algorithms play an important role in several fields of sciences and engineering. Prominent among them are the All-Pairs-Shortest-Paths ( APSP ) 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 paper, we study the applicability of an ear decomposition of graphs to problems such as all-pairs-shortest-paths and minimum cost cycle basis. 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.
关键词：shortest paths; ear decomposition; minimum cycle basis; heterogeneous algorithms