13788

Shortest-Path Queries in Planar Graphs on GPU-Accelerated Architectures

Guillaume Chapuis, Hristo Djidjev
Los Alamos National Laboratory, Los Alamos, NM 87545, USA
arXiv:1503.07192 [cs.DS], (24 Mar 2015)

@article{chapuis2015shortestpath,

   title={Shortest-Path Queries in Planar Graphs on GPU-Accelerated Architectures},

   author={Chapuis, Guillaume and Djidjev, Hristo},

   year={2015},

   month={mar},

   archivePrefix={"arXiv"},

   primaryClass={cs.DS}

}

Download Download (PDF)   View View   Source Source   

620

views

We develop an efficient parallel algorithm for answering shortest-path queries in planar graphs and implement it on a multi-node CPU/GPU clusters. The algorithm uses a divide-and-conquer approach for decomposing the input graph into small and roughly equal subgraphs and constructs a distributed data structure containing shortest distances within each of those subgraphs and between their boundary vertices. For a planar graph with $n$ vertices, that data structure needs $O(n)$ storage per processor and allows queries to be answered in $O(n^{1/4})$ time.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: