Reachability preserving compression for dynamic graph

DOI10.1016/J.INS.2020.02.028MaRDI QIDQ2660982zbMATH OpenOpenAlexFDO

Authors Yuzhi Liang, Chen Chen, Yukun Wang, Kai Lei, Min Yang, 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

compressed graph maintenancedynamic graphgraph queryquery preserving graph compression

Mathematics Subject Classification ID

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

Recommendations

• Improved Dynamic Reachability Algorithms for Directed Graphs
• Faster fully dynamic transitive closure in practice
• Simple efficient graph compression schemes for dense and complement graphs
• Tight and simple web graph compression for forward and reverse neighbor queries
• Speeding up algorithms on compressed web graphs

Cites work

• A fully dynamic reachability algorithm for directed graphs with an almost linear update time
• A strong-connectivity algorithm and its applications in data flow analysis
• Depth-First Search and Linear Graph Algorithms
• Dynamic shortest paths and transitive closure: algorithmic techniques and data structures
• scientific article; zbMATH DE number 2185626 (Why is no real title available?)
• scientific article; zbMATH DE number 432745 (Why is no real title available?)
• scientific article; zbMATH DE number 1306899 (Why is no real title available?)
• Maximum Steiner connected k-core query processing based on graph compression

Cited in

(4)

• Compression of dynamic graphs generated by a duplication model
• FCA in a logical programming setting for visualization-oriented graph compression
• Maximum Steiner connected k-core query processing based on graph compression
• Distance-preserving graph compression techniques

Describes a project that uses

Uses Software

• WebGraph
• SNAP

This page was built for publication: Reachability preserving compression for dynamic graph

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