Show simple item record

dc.contributor.authorKatz, Gary J.en_US
dc.contributor.authorJr., Joseph T. Kideren_US
dc.contributor.editorDavid Luebke and John Owensen_US
dc.date.accessioned2013-10-28T10:19:26Z
dc.date.available2013-10-28T10:19:26Z
dc.date.issued2008en_US
dc.identifier.isbn978-3-905674-09-5en_US
dc.identifier.issn1727-3471en_US
dc.identifier.urihttp://dx.doi.org/10.2312/EGGH/EGGH08/047-055en_US
dc.description.abstractThe 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.publisherThe Eurographics Associationen_US
dc.subjectCategories and Subject Descriptors (according to ACM CCS): I.3.1 [Computer Graphics]: Hardware Architecture Graphics Processors Parallel processing G.2.2 [Graph Theory]: Graph algorithmsen_US
dc.titleAll-Pairs Shortest-Paths for Large Graphs on the GPUen_US
dc.description.seriesinformationGraphics Hardwareen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record