2014/04/17 by Florian Merz, F. Merz, Peter Sanders +2 · 1 citation
Computer Science · #Advanced Database Systems and Queries #Algorithms and Data Compression #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS
paper · pdf · doi:10.48550/arxiv.1404.4465
arxiv created 2014/04/17 · openalex publication_date 2014/04/17 · arxiv updated 2014/04/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We develop the data structure PReaCH (for Pruned Reachability Contraction Hierarchies) which supports reachability queries in a directed graph, i.e., it supports queries that ask whether two nodes in the graph are connected by a directed path. PReaCH adapts the contraction hierarchy speedup techniques for shortest path queries to the reachability setting. The resulting approach is surprisingly simple and guarantees linear space and near linear preprocessing time. Orthogonally to that, we improve existing pruning techniques for the search by gathering more information from a single DFS-traversal of the graph. PReaCH-indices significantly outperform previous data structures with comparable preprocessing cost. Methods with faster queries need significantly more preprocessing time in particular for the most difficult instances.