On the Approximation of Shortest Common Supersequences and Longest Common Subsequences
From MaRDI portal
Publication:4857599
DOI10.1137/S009753979223842XzbMath0853.68112WikidataQ61067916 ScholiaQ61067916MaRDI QIDQ4857599
Publication date: 2 January 1997
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Parallel algorithms in computer science (68W10)
Related Items (52)
Deposition and extension approach to find longest common subsequence for thousands of long sequences ⋮ Split-Plot Designs for Robotic Serial Dilution Assays ⋮ Beam search for the longest common subsequence problem ⋮ Average-case analysis via incompressibility ⋮ On the longest common rigid subsequence problem ⋮ RNA multiple structural alignment with longest common subsequences ⋮ Novel evolutionary models and applications to sequence alignment problems ⋮ A beam search for the shortest common supersequence problem guided by an approximate expected length calculation ⋮ A note on the precedence-constrained class sequencing problem ⋮ Longest common subsequence problem for unoriented and cyclic strings ⋮ Combined super-/substring and super-/subsequence problems ⋮ Solving longest common subsequence problems via a transformation to the maximum clique problem ⋮ Improved heuristics and a genetic algorithm for finding short supersequences ⋮ The constrained shortest common supersequence problem ⋮ Variants of constrained longest common subsequence ⋮ The multiple sequence sets: Problem and heuristic algorithms ⋮ On the Longest Common Parameterized Subsequence ⋮ On the parameterized complexity of the repetition free longest common subsequence problem ⋮ An approximate \(A^{\ast}\) algorithm and its application to the SCS problem. ⋮ Exact algorithms for the repetition-bounded longest common subsequence problem ⋮ New results for the longest haplotype reconstruction problem ⋮ Approximability of constrained LCS ⋮ A hyper-heuristic for the longest common subsequence problem ⋮ Exact algorithms for the master ring problem ⋮ Unnamed Item ⋮ The multi-spreader crane scheduling problem: partitions and supersequences ⋮ On the complexity of finding common approximate substrings. ⋮ Algorithms for computing variants of the longest common subsequence problem ⋮ On the approximation of longest common nonsupersequences and shortest common nonsubsequences ⋮ Distribution of the length of the longest common subsequence of two multi-state biological sequences ⋮ Finding the longest common subsequence for multiple biological sequences by ant colony optimization ⋮ Restricted Common Superstring and Restricted Common Supersequence ⋮ A large neighborhood search heuristic for the longest common subsequence problem ⋮ Minimum cost multi-product flow lines ⋮ New efficient algorithms for the LCS and constrained LCS problems ⋮ The complexity of flood filling games ⋮ Complexity issues in vertex-colored graph pattern matching ⋮ An improved algorithm for the longest common subsequence problem ⋮ Finite automata based algorithms on subsequences and supersequences of degenerate strings ⋮ Listing Center Strings Under the Edit Distance Metric ⋮ On the complexity of comparing evolutionary trees ⋮ A new efficient algorithm for computing the longest common subsequence ⋮ Approximating Minimum Reset Sequences ⋮ A learning algorithm for the longest common subsequence problem ⋮ Maximum Motif Problem in Vertex-Colored Graphs ⋮ On the approximability of the maximum agreement subtree and maximum compatible tree problems ⋮ Backdoors to planning ⋮ On the longest common parameterized subsequence ⋮ On the approximation of largest common subtrees and largest common point sets ⋮ Comparing incomplete sequences via longest common subsequence ⋮ Anytime algorithms for the longest common palindromic subsequence problem ⋮ Some MAX SNP-hard results concerning unordered labeled trees
This page was built for publication: On the Approximation of Shortest Common Supersequences and Longest Common Subsequences
