On the Approximation of Shortest Common Supersequences and Longest Common Subsequences

DOI10.1137/S009753979223842XzbMATH Open0853.68112WikidataQ61067916 ScholiaQ61067916MaRDI QIDQ4857599FDOQ4857599

Publication date: 2 January 1997

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Recommendations

On the approximation of shortest common supersequences and longest common subsequences
On the approximation of longest common nonsupersequences and shortest common nonsubsequences
scientific article; zbMATH DE number 827942
On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
Algorithms for Computing Variants of the Longest Common Subsequence Problem
scientific article; zbMATH DE number 5545474
On the longest common parameterized subsequence
On the Longest Common Parameterized Subsequence

Kolmogorov complexity NP-hard problems longest common subsequences shortest common supersequences

Analysis of algorithms and problem complexity (68Q25) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Parallel algorithms in computer science (68W10)

Cited In (55)

Average-case analysis via incompressibility
Weighted shortest common supersequence problem revisited
Algorithms and hardness for the longest common subsequence of three strings and related problems
Improved heuristics and a genetic algorithm for finding short supersequences
The constrained shortest common supersequence problem
The multi-spreader crane scheduling problem: partitions and supersequences
Split-plot designs for robotic serial dilution assays
The multiple sequence sets: Problem and heuristic algorithms
A new efficient algorithm for computing the longest common subsequence
Comparing incomplete sequences via longest common subsequence
New efficient algorithms for the LCS and constrained LCS problems
A beam search for the shortest common supersequence problem guided by an approximate expected length calculation
On the longest common rigid subsequence problem
Backdoors to planning
New results for the longest haplotype reconstruction problem
Title not available (Why is that?)
Solving longest common subsequence problems via a transformation to the maximum clique problem
On the longest common parameterized subsequence
Novel evolutionary models and applications to sequence alignment problems
Beam search for the longest common subsequence problem
Restricted common superstring and restricted common supersequence
Variants of constrained longest common subsequence
On the parameterized complexity of the repetition free longest common subsequence problem
Finding the longest common subsequence for multiple biological sequences by ant colony optimization
Approximability of constrained LCS
A hyper-heuristic for the longest common subsequence problem
A note on the precedence-constrained class sequencing problem
Combined super-/substring and super-/subsequence problems
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
Finite automata based algorithms on subsequences and supersequences of degenerate strings
A large neighborhood search heuristic for the longest common subsequence problem
Complexity issues in vertex-colored graph pattern matching
On the approximability of the maximum agreement subtree and maximum compatible tree problems
Exact algorithms for the repetition-bounded longest common subsequence problem
Some MAX SNP-hard results concerning unordered labeled trees
The complexity of flood filling games
Anytime algorithms for the longest common palindromic subsequence problem
RNA multiple structural alignment with longest common subsequences
Longest common subsequence problem for unoriented and cyclic strings
An improved algorithm for the longest common subsequence problem
Approximating minimum reset sequences
Algorithms for computing variants of the longest common subsequence problem
Minimum cost multi-product flow lines
An approximate \(A^{\ast}\) algorithm and its application to the SCS problem.
Listing center strings under the edit distance metric
Maximum Motif Problem in Vertex-Colored Graphs
Deposition and extension approach to find longest common subsequence for thousands of long sequences
On the approximation of largest common subtrees and largest common point sets
Exact algorithms for the master ring problem
On the Longest Common Parameterized Subsequence
A learning algorithm for the longest common subsequence problem
On the complexity of comparing evolutionary trees
On the complexity of finding common approximate substrings.
Title not available (Why is that?)

This page was built for publication: On the Approximation of Shortest Common Supersequences and Longest Common Subsequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4857599)