All-Pairs Shortest Path algorithms for planar graph for GPU-accelerated clusters ?
We develop a new approach for the All-Pairs Shortest Path problem in planar graphs. We target execution on large CPUGPU clusters and graphs with millions of vertices. We design a centralized (master/slave) and a decentralized (distributed) version. Our algorithms are work-efficient and allow a high-degree of parallelism. Our algorithms are significantly faster than the previous ones.
planar graphs all-pairs shortest path problem gpgpu parallel computing floydwarshall algorithm distributed computing algorithm analysis