All-Pairs Shortest-Paths for Large Graphs on the GPU
| dc.contributor.author | Katz, Gary J. | en_US |
| dc.contributor.author | Jr., Joseph T. Kider | en_US |
| dc.contributor.editor | David Luebke and John Owens | en_US |
| dc.date.accessioned | 2013-10-28T10:19:26Z | |
| dc.date.available | 2013-10-28T10:19:26Z | |
| dc.date.issued | 2008 | en_US |
| dc.description.abstract | The all-pairs shortest-path problem is an intricate part in numerous practical applications. We describe a shared memory cache efficient GPU implementation to solve transitive closure and the all-pairs shortest-path problem on directed graphs for large datasets. The proposed algorithmic design utilizes the resources available on the NVIDIA G80 GPU architecture using the CUDA API. Our solution generalizes to handle graph sizes that are inherently larger then the DRAM memory available on the GPU. Experiments demonstrate that our method is able to significantly increase processing large graphs making our method applicable for bioinformatics, internet node traffic, social networking, and routing problems. | en_US |
| dc.description.seriesinformation | Graphics Hardware | en_US |
| dc.identifier.isbn | 978-3-905674-09-5 | en_US |
| dc.identifier.issn | 1727-3471 | en_US |
| dc.identifier.uri | https://doi.org/10.2312/EGGH/EGGH08/047-055 | en_US |
| dc.publisher | The Eurographics Association | en_US |
| dc.subject | Categories and Subject Descriptors (according to ACM CCS): I.3.1 [Computer Graphics]: Hardware Architecture Graphics Processors Parallel processing G.2.2 [Graph Theory]: Graph algorithms | en_US |
| dc.title | All-Pairs Shortest-Paths for Large Graphs on the GPU | en_US |
Files
Original bundle
1 - 1 of 1