Shortest Path Approaches for the Longest Common Subsequence of a Set of Strings

The authors investigate the k-LCS problem that is finding a Longest Common Subsequence (LCS) for k given input strings. The problem is known to have practical solutions for k = 2, but for higher dimensions it is not very well explored. They consider the algorithms by Miller and Myers as well as Wu et al. which solve the 2-LCS problem, and shed a new light on their generalization to higher dimensions. First, they redesign both algorithms such that the generalization to higher dimensions becomes natural. Then they present their algorithms for solving the k-LCS problem.