×

Generalized LCS. (English) Zbl 1155.68021

Summary: The Longest Common Subsequence (LCS) is a well studied problem, having a wide range of implementations. Its motivation is in comparing strings. It has long been of interest to devise a similar measure for comparing higher dimensional objects, and more complex structures. In this paper we study the Longest Common Substructure of two matrices and show that this problem is \(\mathcal{NP}\)-hard. We also study the Longest Common Subforest problem for multiple trees including a constrained version, as well. We show \(\mathcal{NP}\)-hardness for \(k>2\) unordered trees in the constrained LCS. We also give polynomial time algorithms for ordered trees and prove a lower bound for any decomposition strategy for \(k\) trees.

MSC:

68P10 Searching and sorting
68T10 Pattern recognition, speech recognition
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Amir, A.; Keselman, D., Maximum agreement subtree in a set of evolutionary trees — metrics and efficient algorithms, SIAM J. Comput., 26, 6, 1656-1669 (1997) · Zbl 0885.68071
[2] Amir, A.; Landau, G. M., Fast parallel and serial multidimensional approximate array matching, Theoret. Comput. Sci., 81, 1, 97-115 (1991) · Zbl 0725.68050
[3] R. Baeza-Yates, Similarity in two-dimensional strings, in: Proc. COOCON, 1998, pp. 319-328; R. Baeza-Yates, Similarity in two-dimensional strings, in: Proc. COOCON, 1998, pp. 319-328 · Zbl 0909.68044
[4] L. Bergroth, H. Hakonen, T. Raita, A survey of longest common subsequence algorithms, in: Proc. 7th Symposium on String Processing and Information Retrieval, SPIRE, 2000, pp. 39-48; L. Bergroth, H. Hakonen, T. Raita, A survey of longest common subsequence algorithms, in: Proc. 7th Symposium on String Processing and Information Retrieval, SPIRE, 2000, pp. 39-48
[5] Bille, P., A Survey on Tree Edit Distance and Related Problems, Theoret. Comput. Sci., 337, 1-3, 217-239 (2005) · Zbl 1078.68152
[6] P. Bille, I.L. Gørtz, The tree inclusion problem: In optimal space and faster, in: Proc. 32nd International Colloquium on Automata, Languages and Programming, 2005, pp. 66-77; P. Bille, I.L. Gørtz, The tree inclusion problem: In optimal space and faster, in: Proc. 32nd International Colloquium on Automata, Languages and Programming, 2005, pp. 66-77 · Zbl 1085.68566
[7] Branden, C.; Tooze, J., Introduction to Protein Structure (1999), Garland Publishing: Garland Publishing New York, NY
[8] Demaine, E.; Mozes, S.; Rossman, B.; Weimann, O., An optimal decomposition algorithm for tree edit distance, ACM Trans. Algorithms (2008)
[9] M. Farach, T.M. Przytycka, M. Thorup, The maximum agreement subtree problem for binary trees, in: Proc. 3rd Annual European Symposium on Algorithms, ESA, 1995, pp. 381-393; M. Farach, T.M. Przytycka, M. Thorup, The maximum agreement subtree problem for binary trees, in: Proc. 3rd Annual European Symposium on Algorithms, ESA, 1995, pp. 381-393
[10] Gabow, H. N.; Tarjan, R. E., Faster scaling algorithms for network problems, SIAM J. Comput., 18, 5, 1013-1036 (1989) · Zbl 0679.68079
[11] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), W.H. Freeman and Co.: W.H. Freeman and Co. New York · Zbl 0411.68039
[12] Harel, D.; Tarjan, R. E., Fast algorithms for finding nearest common ancestors, SIAM J. Comput., 13, 2, 338-355 (1984) · Zbl 0535.68022
[13] Kilpelinen, P.; Mannila, H., Ordered and unordered tree inclusion, SIAM J. Comput., 24, 2, 340-356 (1995) · Zbl 0827.68050
[14] P.N. Klein, Computing the edit distance between unrooted ordered trees, in: Proc. 6th European Symposium on Algorithms, ESA, 1998, pp. 91-102; P.N. Klein, Computing the edit distance between unrooted ordered trees, in: Proc. 6th European Symposium on Algorithms, ESA, 1998, pp. 91-102 · Zbl 0932.68066
[15] Krithivasan, K.; Sitalakshmi, R., Efficient two-dimensional pattern matching in the presence of errors, Inform. Sci., 43, 3, 169-184 (1987)
[16] R.Y. Pinter, O. Rokhlenko, D. Tsur, M. Ziv-Ukelson, Approximate labeled subtree homeomorphism, in: Proc. 15th Symposium on Combinatorial Pattern Matching, CPM, 2004, pp. 59-73; R.Y. Pinter, O. Rokhlenko, D. Tsur, M. Ziv-Ukelson, Approximate labeled subtree homeomorphism, in: Proc. 15th Symposium on Combinatorial Pattern Matching, CPM, 2004, pp. 59-73 · Zbl 1103.68658
[17] T. Richter, A new algorithm for the ordered tree inclusion problem, in: Proc. 8th Symposium on Combinatorial Pattern Matching, CPM, 1997, pp. 150-166; T. Richter, A new algorithm for the ordered tree inclusion problem, in: Proc. 8th Symposium on Combinatorial Pattern Matching, CPM, 1997, pp. 150-166
[18] Shapiro, B. A.; Zhang, K. Z., Comparing multiple RNA secondary structures using tree comparisons, Comput. Appl. Biosci., 6, 4, 309-318 (1990)
[19] Shasha, D.; Zhang, K., Simple fast algorithms for the editing distance between trees and related problems, SIAM J. Comput., 18, 6, 1245-1262 (1989) · Zbl 0692.68047
[20] Steel, M.; Warnow, T., Kaikoura tree theorems: The maximum agreement subtree problem, Inform. Process. Lett., 48, 77-82 (1993) · Zbl 0942.68578
[21] Takahashi, Y.; Satoh, Y.; Suzuki, H.; Sasaki, S., Recognition of largest common structural fragment among a variety of chemical structures, Anal. Sci., 3, 23-28 (1987)
[22] G. Valiente, Simple and efficient tree comparison, Technical Report LSI-01-1-R, Technical University of Catalonia, Department of Software, 2001; G. Valiente, Simple and efficient tree comparison, Technical Report LSI-01-1-R, Technical University of Catalonia, Department of Software, 2001
[23] Valiente, G., Constrained tree inclusion, J. Discrete Algorithms, 3, 2-4, 431-447 (2005) · Zbl 1129.68096
[24] Wagner, R. A.; Fischer, M. J., The string-to-string correction problem, J. ACM, 21, 168-173 (1974) · Zbl 0278.68032
[25] Zhang, K., Algorithm for the constrained editing problem between ordered labeled trees and related problems, Pattern Recognit., 28, 463-478 (1995)
[26] Zhang, K., A constrained edit distance between unordered labeled trees, Algorithmica, 15, 3, 205-222 (1996) · Zbl 0839.68035
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.