2015/03/24 by Guillaume Chapuis, Hristo Djidjev, Chapuis, Guillaume +1
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Graph Theory and Algorithms #cs.DS
paper · pdf · doi:10.48550/arxiv.1503.07192
arxiv created 2015/03/24 · openalex publication_date 2015/03/24 · arxiv updated 2015/03/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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(n1/4) time.