A Specialized Branching and Fathoming Technique for The Longest Common Subsequence Problem
Todd Easton, Abhilash Singireddy · 2007
Abstract⎯Given a set S = {S 1,..., S k} of finite strings, the k-longest common subsequence problem (k-LCSP) seeks a string L of maximum length such that L is a subsequence of each S i for i = 1,..., k. This paper presents a technique, specialized branching, that solves k-LCSP. Specialized branching combines the benefits of both dynamic programming and branch and bound to reduce the search space. For large k, this method is shown to be computationally superior to dynamic programming. Keywords⎯Longest common subsequence, Branch and bound, Dynamic programming 1.