H. Ann, C. Yang, C. Tseng, and C. Hor, Fast algorithms for computing the constrained LCS of run-length encoded strings, Proc. International Conference on Bioinformatics & Computational Biology (BIOCOMP), pp.646-649, 2009.
DOI : 10.1016/j.tcs.2012.01.038

H. Ann, C. Yang, C. Tseng, and C. Hor, A fast and simple algorithm for computing the longest common subsequence of run-length encoded strings, Information Processing Letters, vol.108, issue.6, pp.360-364, 2008.
DOI : 10.1016/j.ipl.2008.07.005

A. Apostolico, G. M. Landau, and S. Skiena, Matching for Run-Length Encoded Strings, Journal of Complexity, vol.15, issue.1, pp.4-16, 1999.
DOI : 10.1006/jcom.1998.0493
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.46.2269

L. Bergroth, H. Hakonen, and T. Raita, A survey of longest common subsequence algorithms, Proceedings Seventh International Symposium on String Processing and Information Retrieval. SPIRE 2000
DOI : 10.1109/SPIRE.2000.878178

P. Berman and G. Schnitger, On the complexity of approximating the independent set problem, Information and Computation, vol.96, issue.1, pp.77-94, 1992.
DOI : 10.1016/0890-5401(92)90056-L

H. L. Bodlaender, R. G. Downey, M. R. Fellows, M. T. Hallett, and H. T. Wareham, Parameterized complexity analysis in computational biology, Bioinformatics, vol.11, issue.1, pp.49-57, 1995.
DOI : 10.1093/bioinformatics/11.1.49

H. L. Bodlaender, R. G. Downey, M. R. Fellows, and H. T. Wareham, The parameterized complexity of sequence alignment and consensus, Theoretical Computer Science, vol.147, issue.1-2, pp.31-54, 1994.
DOI : 10.1016/0304-3975(94)00251-D

P. Bonizzoni, G. D. Vedova, and G. Mauri, Experimenting an approximation algorithm for the LCS, Discrete Applied Mathematics, vol.110, issue.1, pp.13-24, 2001.
DOI : 10.1016/S0166-218X(00)00300-0

H. Bunke and J. Csirik, An improved algorithm for computing the edit distance of run-length coded strings, Information Processing Letters, vol.54, issue.2, pp.93-96, 1995.
DOI : 10.1016/0020-0190(95)00005-W

V. Freschi and A. Bogliolo, Longest common subsequence between run-length-encoded strings: a??new algorithm with improved parallelism, Information Processing Letters, vol.90, issue.4, pp.167-173, 2004.
DOI : 10.1016/j.ipl.2004.02.011

M. M. Halldórsson, Approximation via partitioning, School of Information Science Japan Advanced Institute of Science and Technology, 1995.

P. Hsu, K. Chen, and K. Chao, Finding all approximate gapped palindromes, Proc. 20th International Symposium Algorithms and Computation (ISAAC) number 5878 in Lecture Notes in Computer Science, pp.1084-1093, 2009.
DOI : 10.1007/978-3-642-10631-6_109

G. S. Huang, J. J. Liu, and Y. L. Wang, Sequence Alignment Algorithms for Run-Length-Encoded Strings, Proc. 14th Annual International Computing and Combinatorics Conference (COCOON) number 5092 in Lecture Notes in Computer Science, pp.319-330, 2008.
DOI : 10.1007/978-3-540-69733-6_32

T. Jiang and M. Li, On the Approximation of Shortest Common Supersequences and Longest Common Subsequences, SIAM Journal on Computing, vol.24, issue.5, pp.1122-1139, 1995.
DOI : 10.1137/S009753979223842X

P. Hsu, K. Chen, and K. Chao, Finding all approximate gapped palindromes, Proc. 21th International Symposium Algorithms and Computation (ISAAC) number 6507 in Lecture Notes in Computer Science, pp.339-350, 2010.
DOI : 10.1007/978-3-642-10631-6_109

J. W. Kim, A. Amir, G. M. Landau, and K. Park, Computing similarity of run-length encoded strings with affine gap penalty, Theoretical Computer Science, vol.395, issue.2-3, pp.268-282, 2008.
DOI : 10.1016/j.tcs.2008.01.008

J. J. Liu, G. S. Huang, and Y. L. Wang, A fast algorithm for finding the positions of all squares in a run-length encoded string, Theoretical Computer Science, vol.410, issue.38-40, pp.3942-3948, 2009.
DOI : 10.1016/j.tcs.2009.05.032

J. J. Liu, G. S. Huang, Y. L. Wang, and R. C. Lee, Edit distance for a run-length-encoded string and an uncompressed string, Information Processing Letters, vol.105, issue.1, pp.12-16, 2007.
DOI : 10.1016/j.ipl.2007.07.006

J. J. Liu, Y. L. Wang, and R. C. Lee, Finding a longest common subsequence between a run-length-encoded string and an uncompressed string, Journal of Complexity, vol.24, issue.2, pp.173-184, 2008.
DOI : 10.1016/j.jco.2007.06.003

D. Maier, The Complexity of Some Problems on Subsequences and Supersequences, Journal of the ACM, vol.25, issue.2, pp.322-336, 1978.
DOI : 10.1145/322063.322075

W. Matsubara, S. Inenaga, A. Ishino, A. Shinohara, T. Nakamura et al., Efficient algorithms to compute compressed longest common substrings and compressed palindromes, Theoretical Computer Science, vol.410, issue.8-10, pp.900-913, 2009.
DOI : 10.1016/j.tcs.2008.12.016

J. S. Mitchell, A geometric shortest path problem, with application to computing a longest common subsequence in run-length encoded strings, 1997.

K. Pietrzak, On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems, Journal of Computer and System Sciences, vol.67, issue.4, pp.757-771, 2003.
DOI : 10.1016/S0022-0000(03)00078-3