Applications of Ear Decomposition to Efficient Heterogeneous Algorithms for Shortest Path/Cycle Problems
| Autor: | Meher Chaitanya, Kishore Kothapalli, Debajyoti Bera, Debarshi Dutta |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Theoretical computer science
Speedup Computer science Computation 010103 numerical & computational mathematics 02 engineering and technology Ear decomposition Parallel computing 01 natural sciences Graph Method of undetermined coefficients Shortest path problem Scalability 0202 electrical engineering electronic engineering information engineering Cycle basis 020201 artificial intelligence & image processing Algorithm design 0101 mathematics Algorithm Implementation |
| Zdroj: | IPDPS Workshops |
| ISSN: | 2185-2847 2185-2839 |
| DOI: | 10.15803/ijnc.8.1_73 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|