Grammar-based graph compression
Tài liệu tham khảo
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
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
Š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
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
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