The Complexity of Some Problems on Subsequences and Supersequences

Cited in

(only showing first 100 items - show all)

New Error Tolerant Method for Search of Long Repeats in DNA Sequences
On the inadequacy of tournament algorithms for the N-SCS problem
Hardness and approximation of multiple sequence alignment with column score
An approximate \(A^{\ast}\) algorithm and its application to the SCS problem.
Combinatorial algorithms for subsequence matching: a survey
Computing a longest common subsequence for a set of strings
Searching and inferring colorful topological motifs in vertex-colored graphs
Finding diverse strings and longest common subsequences in a graph
Subsequences with generalised gap constraints: upper and lower complexity bounds
Analogical proportions in a lattice of sets of alignments built on the common subwords in a finite language
Listing center strings under the edit distance metric
k-universality of regular languages revisited
Consensus sequences based on plurality rule
Constrained LCS: Hardness and Approximation
Subsequence matching and analysis problems for formal languages
FACC: a novel finite automaton based on cloud computing for the multiple longest common subsequences search
Searching subsequences
On the approximation of largest common subtrees and largest common point sets
Nearly \(k\)-universal words -- investigating a part of Simon's congruence
A hybrid genetic algorithm for the repetition free longest common subsequence problem
Beam-ACO for the repetition-free longest common subsequence problem
The string merging problem
On the Longest Common Parameterized Subsequence
Finding shuffle words that represent optimal scheduling of shared memory access
Comparing bacterial genomes from linear orders of patterns
Efficient algorithms for finding a longest common increasing subsequence
On the approximation of protein threading
A branch-and-bound framework for unsupervised common event discovery
Sequence matching with binary codes
Consistent subsequences and supersequences
On the approximation of shortest common supersequences and longest common subsequences
Concordance and consensus
Weighted shortest common supersequence problem revisited
Efficient algorithms for finding interleaving relationship between sequences
On the complexity of learning strings and sequences
On the complexity of finding common approximate substrings.
The edit distance to k-subsequence universality
Tractability and hardness of flood-filling games on trees
Algorithms and hardness for the longest common subsequence of three strings and related problems
Approximate periods of strings
A simple algorithm for the constrained sequence problems
Constrained sequence analysis algorithms in computational biology
Improved heuristics and a genetic algorithm for finding short supersequences
Comparison of strings belonging to the same family
A compact DAG for storing and searching maximal common subsequences
The constrained shortest common supersequence problem
Longest common subsequence with gap constraints
The multi-spreader crane scheduling problem: partitions and supersequences
Constrained string editing
APPLICATION-SPECIFIC ARRAY PROCESSORS FOR THE LONGEST COMMON SUBSEQUENCE PROBLEM OF THREE SEQUENCES ∗ †
Efficient algorithms for enumerating maximal common subsequences of two strings
A new efficient algorithm for computing the longest common subsequence
Nearly \(k\)-universal words -- investigating a part of Simon's congruence
An \(A^\ast\) search algorithm for the constrained longest common subsequence problem
String Covering: A Survey
Generalized random shapelet forests
Hardness results for the center and median string problems under the weighted and unweighted edit distances
On recognising words that are squares for the shuffle product
New efficient algorithms for the LCS and constrained LCS problems
A\textsuperscript{*}-based compilation of relaxed decision diagrams for the longest common subsequence problem
Finding common structured patterns in linear graphs
Parameterized complexity and approximability of the longest compatible sequence problem
Dynamic programming algorithms for the mosaic longest common subsequence problem
On the longest common rigid subsequence problem
A beam search for the shortest common supersequence problem guided by an approximate expected length calculation
The merged longest common increasing subsequence problem
A policy-based learning beam search for combinatorial optimization
On searching and indexing sequences of temporal intervals
More on the complexity of common superstring and supersequence problems
The shortest common supersequence problem over binary alphabet is NP- complete
Fast algorithms for computing the constrained LCS of run-length encoded strings
A new practical linear space algorithm for the longest common subsequence problem
scientific article; zbMATH DE number 809154 (Why is no real title available?)
Longest Common Subsequence with Gap Constraints
Absent subsequences in words
Longest common subsequences
On the complexity of approximating the independent set problem (extended abstract)
Finding the longest common nonsuperstring in linear time
Feasibility recovery for the unit-capacity constrained permutation problem
The unit-capacity constrained permutation problem
On the longest common parameterized subsequence
Novel evolutionary models and applications to sequence alignment problems
Solving longest common subsequence problems via a transformation to the maximum clique problem
scientific article; zbMATH DE number 7758340 (Why is no real title available?)
Beam search for the longest common subsequence problem
Variants of constrained longest common subsequence
On the parameterized complexity of the repetition free longest common subsequence problem
Restricted common superstring and restricted common supersequence
Finding the longest common subsequence for multiple biological sequences by ant colony optimization
Approximability of constrained LCS
On the generalized constrained longest common subsequence problems
A hyper-heuristic for the longest common subsequence problem
Algorithms and complexity on indexing founder graphs
Combined super-/substring and super-/subsequence problems
Subsequences in bounded ranges: matching and analysis problems
On the approximation of longest common nonsupersequences and shortest common nonsubsequences
About the design of oligo-chips
Finite automata based algorithms on subsequences and supersequences of degenerate strings
The consensus string problem for a metric is NP-complete
Existential Definability over the Subword Ordering

This page was built for publication: The Complexity of Some Problems on Subsequences and Supersequences

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