Generalized LCS

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 N P -hard. We also study the Longest Common Subforest problem for multiple trees including a constrained version, as well. We show N P -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.

Authors

• Amihood Amir
• Tzvika Hartman
• Oren Kapah
• B. Riva Shalom
• Dekel Tsur

Keywords

• Longest common subsequence
• Matrices
• Trees
• Non crossing matching