Reachability preserving compression for dynamic graph

DOI10.1016/j.ins.2020.02.028zbMath1457.68219OpenAlexW3005994946MaRDI QIDQ2660982

Chen Chen, Kai Lei, Min Yang, Yuzhi Liang, Yukun Wang, Ziyu Lyu

Publication date: 31 March 2021

Published in: Information Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ins.2020.02.028

zbMATH Keywords

dynamic graphgraph querycompressed graph maintenancequery preserving graph compression

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Uses Software

• SNAP
• WebGraph

Cites Work

• Dynamic shortest paths and transitive closure: algorithmic techniques and data structures
• A strong-connectivity algorithm and its applications in data flow analysis
• A Fully Dynamic Reachability Algorithm for Directed Graphs with an Almost Linear Update Time
• 基于图压缩的最大Steiner连通 k 核查询处理
• Depth-First Search and Linear Graph Algorithms
• Unnamed Item
• Unnamed Item
• Unnamed Item