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

DOI10.1007/978-3-319-26520-9_5MaRDI QIDQ3304759zbMATH OpenOpenAlexFDO

Authors Guillaume Chapuis, Hristo N. Djidjev

Publication date 3 August 2020

Published in Large-Scale Scientific Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1503.07192

zbMATH Keywords

distributed computingGPU computinggraph algorithmsgraph partitioningshortest path problems

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Abstract: 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.

Recommendations

• Shortest path queries in planar graphs
• Multiple-source shortest paths in planar graphs
• scientific article; zbMATH DE number 176745
• Short path queries in planar graphs in constant time

Cites work

• A note on two problems in connexion with graphs
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• Parallel Multilevel series k-Way Partitioning Scheme for Irregular Graphs
• Planar graph decomposition and all pairs shortest paths
• Shortest path queries in planar graphs

Cited in

(2)

• Shortest path queries in planar graphs
• Solving path problems on the GPU

This page was built for publication: Shortest-Path Queries in Planar Graphs on GPU-Accelerated Architectures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3304759)