Grammar-based graph compression

Wood, 2012, Query languages for graph databases, SIGMOD Record, 4, 50, 10.1145/2206869.2206879

Lohrey, 2012, Algorithmics on SLP-compressed strings: a survey, Groups Complex. Cryptol., 4, 241, 10.1515/gcc-2012-0016

Lohrey, 2015, Grammar-based tree compression, 46

Charikar, 2005, The smallest grammar problem, IEEE Trans. Inf. Theory, 51, 2554, 10.1109/TIT.2005.850116

Larsson, 2000, Off-line dictionary-based compression, Proc. IEEE, 1722, 10.1109/5.892708

Lohrey, 2013, XML tree structure compression using repair, Inf. Syst., 38, 1150, 10.1016/j.is.2013.06.006

Weisfeiler, 1968, A reduction of a graph to a canonical form and an algebra arising during this reduction, Nauchno-Techn. Inf., Seriya 2, 12

Grabowski, 2014, Tight and simple web graph compression for forward and reverse neighbor queries, Discrete Appl. Math., 163, 298, 10.1016/j.dam.2013.05.028

Drewes, 1997, Hyperedge replacement graph grammars, 95

Peshkin, 2007, Structure induction by lossless graph compression, 53

Nevill-Manning, 1997, Identifying hierarchical structure in sequences: a linear-time algorithm, J. Artif. Intell. Res., 7, 67, 10.1613/jair.374

Liefke, 2000, XMILL: an efficient compressor for XML data, 153

Boldi, 2004, The webgraph framework I: compression techniques, 595

Boldi, 2009, Permuting web graphs, 116

Apostolico, 2009, Graph compression by BFS, Algorithms, 2, 1031, 10.3390/a2031031

Šimeček, 2009, Sparse matrix computations using the quadtree storage format, 168

Maserrat, 2012

Fernández, 2010, RDF compression: basic approaches, 1091

Martínez-Prieto, 2012, Compression of RDF dictionaries, 340

Urbani, 2013, Scalable RDF data compression with mapreduce, Concurr. Comput.: Pract. Exp., 25, 24, 10.1002/cpe.2840

Álvarez-García, 2017, A succinct data structure for self-indexing ternary relations, J. Discrete Algorithms, 43, 38, 10.1016/j.jda.2016.10.002

Papadimitriou, 1986, A note on succinct representations of graphs, Inf. Control, 71, 181, 10.1016/S0019-9958(86)80009-2

Lengauer, 1992, The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems, J. Comput. Syst. Sci., 44, 63, 10.1016/0022-0000(92)90004-3

Lengauer, 1988, Efficient solution of connectivity problems on hierarchically defined graphs, SIAM J. Comput., 17, 1063, 10.1137/0217068

Marathe, 1998, Approximation algorithms for pspace-hard hierarchically and periodically specified problems, SIAM J. Comput., 27, 1237, 10.1137/S0097539795285254

Habel, 1992

Lohrey, 2006, The complexity of tree automata and XPath on grammar-compressed trees, Theor. Comput. Sci., 363, 196, 10.1016/j.tcs.2006.07.024

Lohrey, 2012, Parameter reduction and automata evaluation for grammar-compressed trees, J. Comput. Syst. Sci., 78, 1651, 10.1016/j.jcss.2012.03.003

Edmonds, 1965, Paths, trees, and flowers, Canad. J. Math., 17, 449, 10.4153/CJM-1965-045-4

Elias, 1975, Universal codeword sets and representations of the integers, IEEE Trans. Inf. Theory, 21, 194, 10.1109/TIT.1975.1055349

Engelfriet, 1997, Node replacement graph grammars, 1

Habel, 1993, A comparison of compatible, finite, and inductive graph properties, Theor. Comput. Sci., 110, 145, 10.1016/0304-3975(93)90354-V

Tarjan, 1972, Depth-first search and linear graph algorithms, SIAM J. Comput., 1, 146, 10.1137/0201010

Thompson, 1968, Regular expression search algorithm, Commun. ACM, 11, 419, 10.1145/363347.363387

Jez, 2016, Recompression: a simple and powerful technique for word equations, J. ACM, 63, 4:1, 10.1145/2743014

Böttcher, 2016, Incremental updates on compressed XML, 1026

Lohrey, 2015, Compressed tree canonization, 337