2023/11/01 by Loukas Georgiadis, Evangelos Kosinas, Georgiadis, Loukas +3
Computer Science · #Caching and Content Delivery #Data Structures and Algorithms (cs.DS) #Distributed systems and fault tolerance #FOS: Computer and information sciences #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.2311.00854
openalex publication_date 2023/11/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the problem of efficiently answering strong connectivity queries under two vertex failures. Given a directed graph G with n vertices, we provide a data structure with O(nh) space and O(h) query time, where h is the height of a decomposition tree of G into strongly connected subgraphs. This immediately implies data structures with O(n logn) space and O(logn) query time for graphs of constant treewidth, and O(n3/2) space and O(√(n)) query time for planar graphs. For general directed graphs, we give a refined version of our data structure that achieves O(n√(m)) space and O(√(m)) query time, where m is the number of edges of the graph. We also provide some simple BFS-based heuristics that seem to work remarkably well in practice. In the experimental part, we first evaluate various methods to construct a decomposition tree with small height h in practice. Then we provide efficient implementations of our data structures, and evaluate their empirical performance by conducting an extensive experimental study on graphs taken from real-world applications.