Abstract | ||
---|---|---|
In this paper we study the parallel computational complexity of some methods for compressing data via textual substitution. We show that the Ziv-Lempel algorithm and two standard variations are P-complete. Hence an efficient parallelization of these algorithms is not possible unless P = NC. |
Year | DOI | Venue |
---|---|---|
1994 | 10.1016/0304-3975(94)90106-6 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
data compression,P-complete problem | Journal | 127 |
Issue | ISSN | Citations |
1 | Theoretical Computer Science | 18 |
PageRank | References | Authors |
1.17 | 5 | 1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Sergio De Agostino | 1 | 102 | 16.51 |