solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看3625次
A parallel algorithm for the constrained shortest path problem on lattice graphs. (arXiv:1511.06441v2 [math.OC] UPDATED)
来源于:arXiv
The edges of a graph are assigned weights and passage times which are assumed
to be positive integers. We present a parallel algorithm for finding the
shortest path whose total weight is smaller than a pre-determined value. In
each step the processing elements are not analyzing the entire graph. Instead
they are focusing on a subset of vertices called {\em 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$. 查看全文>>