• Login
    View Item 
    •   Eurographics DL Home
    • Eurographics Workshops and Symposia
    • EGGH: SIGGRAPH/Eurographics Workshop on Graphics Hardware
    • EGGH08: SIGGRAPH/Eurographics Workshop on Graphics Hardware 2008
    • View Item
    •   Eurographics DL Home
    • Eurographics Workshops and Symposia
    • EGGH: SIGGRAPH/Eurographics Workshop on Graphics Hardware
    • EGGH08: SIGGRAPH/Eurographics Workshop on Graphics Hardware 2008
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    All-Pairs Shortest-Paths for Large Graphs on the GPU

    Thumbnail
    View/Open
    047-055.pdf (168.3Kb)
    Date
    2008
    Author
    Katz, Gary J.
    Jr., Joseph T. Kider
    Pay-Per-View via TIB Hannover:

    Try if this item/paper is available.

    Metadata
    Show full item record
    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.
    BibTeX
    @inproceedings {EGGH:EGGH08:047-055,
    booktitle = {Graphics Hardware},
    editor = {David Luebke and John Owens},
    title = {{All-Pairs Shortest-Paths for Large Graphs on the GPU}},
    author = {Katz, Gary J. and Jr., Joseph T. Kider},
    year = {2008},
    publisher = {The Eurographics Association},
    ISSN = {1727-3471},
    ISBN = {978-3-905674-09-5},
    DOI = {10.2312/EGGH/EGGH08/047-055}
    }
    URI
    http://dx.doi.org/10.2312/EGGH/EGGH08/047-055
    Collections
    • EGGH08: SIGGRAPH/Eurographics Workshop on Graphics Hardware 2008

    Eurographics Association copyright © 2013 - 2020 
    Send Feedback | Contact - Imprint | Data Privacy Policy | Disable Google Analytics
    Theme by @mire NV
    System hosted at  Graz University of Technology.
    TUGFhA
     

     

    Browse

    All of Eurographics DLCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    LoginRegister

    BibTeX | TOC

    Create BibTeX Create Table of Contents

    Eurographics Association copyright © 2013 - 2020 
    Send Feedback | Contact - Imprint | Data Privacy Policy | Disable Google Analytics
    Theme by @mire NV
    System hosted at  Graz University of Technology.
    TUGFhA