14984

A parallel algorithm for the constrained shortest path problem on lattice graphs

Ivan Matic
Department of Mathematics, Baruch College, City University of New York, One Bernard Baruch Way, New York, NY 10010, USA
arXiv:1511.06441 [math.OC], (19 Nov 2015)

@article{matic2015parallel,

   title={A parallel algorithm for the constrained shortest path problem on lattice graphs},

   author={Matic, Ivan},

   year={2015},

   month={nov},

   archivePrefix={"arXiv"},

   primaryClass={math.OC}

}

Download Download (PDF)   View View   Source Source   

746

views

We present a parallel algorithm for finding the shortest path whose total weight is smaller than a pre-determined value. The passage times over the edges are assumed to be positive integers. In each step the processing elements are not analyzing the entire graph. Instead they are focusing on a subset of vertices called active vertices. The set of active vertices at time $t$ is related to the boundary of the ball $B_t$ of radius $t$ in the first passage percolation metric. Although it is believed that the number of active vertices is an order of magnitude smaller than the size of the graph, we prove that this need not be the case with an example of a graph for which the active vertices form a large fractal. We analyze an OpenCL implementation of the algorithm on GPU for cubes in $mathbb Z^d$.
VN:F [1.9.22_1171]
Rating: 1.0/5 (1 vote cast)
A parallel algorithm for the constrained shortest path problem on lattice graphs, 1.0 out of 5 based on 1 rating

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: