Grammar-based graph compression

作者：

Highlights：

• We present a linear time graph compression algorithm.

• The algorithm produces straight-line graph grammars.

• A resulting grammar can be, in the limit, exponentially smaller than the given graph.

• Certain queries such as reachability queries can be performed directly on the grammar, without prior decompression.

摘要

•We present a linear time graph compression algorithm.•The algorithm produces straight-line graph grammars.•A resulting grammar can be, in the limit, exponentially smaller than the given graph.•Certain queries such as reachability queries can be performed directly on the grammar, without prior decompression.

论文关键词：Graph compression,Straight-line context-free hyperedge replacement grammar

论文评审过程：Received 16 March 2017, Revised 14 February 2018, Accepted 11 March 2018, Available online 19 March 2018, Version of Record 19 April 2018.

论文官网地址：https://doi.org/10.1016/j.is.2018.03.002