Shortest-Path Queries in Planar Graphs on GPU-Accelerated Architectures
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}
}
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.
March 28, 2015 by hgpu
