The Complexity of Some Problems on Subsequences and Supersequences

Cited in

(only showing first 100 items - show all)

The constrained longest common subsequence problem
On the longest common parameterized subsequence
Optimizing glass coating lines: MIP model and valid inequalities
New algorithms for the LCS problem
Consensus supertrees: The synthesis of rooted trees containing overlapping sets of labeled leaves
Constrained string editing
The string merging problem
The shortest common supersequence problem over binary alphabet is NP- complete
On the inadequacy of tournament algorithms for the N-SCS problem
On the complexity of approximating the independent set problem
Consensus sequences based on plurality rule
The shortest common nonsubsequence problem is NP-complete
On the approximation of protein threading
The computation of consensus patterns in \(DNA\) sequences
More on the complexity of common superstring and supersequence problems
The parameterized complexity of sequence alignment and consensus
Improved heuristics and a genetic algorithm for finding short supersequences
An approximate \(A^{\ast}\) algorithm and its application to the SCS problem.
On the complexity of finding common approximate substrings.
On the approximation of largest common subtrees and largest common point sets
Dynamic programming algorithms for RNA secondary structure prediction with pseudoknots
Optimality regions and fluctuations for Bernoulli last passage models
An efficient algorithm for LCS problem between two arbitrary sequences
Generalized random shapelet forests
On searching and indexing sequences of temporal intervals
Feasibility recovery for the unit-capacity constrained permutation problem
The unit-capacity constrained permutation problem
An improved algorithm for the longest common subsequence problem
About the design of oligo-chips
Scheduling tasks on a flexible manufacturing machine to minimize tool change delays
Comparison of strings belonging to the same family
On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
FACC: a novel finite automaton based on cloud computing for the multiple longest common subsequences search
Nearly \(k\)-universal words -- investigating a part of Simon's congruence
A\textsuperscript{*}-based compilation of relaxed decision diagrams for the longest common subsequence problem
A beam search for the shortest common supersequence problem guided by an approximate expected length calculation
A branch-and-bound framework for unsupervised common event discovery
Exact algorithms for the repetition-bounded longest common subsequence problem
The multi-spreader crane scheduling problem: partitions and supersequences
An \(A^\ast\) search algorithm for the constrained longest common subsequence problem
Anytime algorithms for the longest common palindromic subsequence problem
Tractability and hardness of flood-filling games on trees
Efficient algorithms for finding interleaving relationship between sequences
RNA multiple structural alignment with longest common subsequences
A simple algorithm for the constrained sequence problems
A hardness result and new algorithm for the longest common palindromic subsequence problem
An efficient dynamic programming algorithm for the generalized LCS problem with multiple substring exclusive constraints
A hybrid genetic algorithm for the repetition free longest common subsequence problem
Multiple genome rearrangement by swaps and by element duplications
Minimum cost multi-product flow lines
Hardness results for the center and median string problems under the weighted and unweighted edit distances
Searching subsequences
Solving longest common subsequence problems via a transformation to the maximum clique problem
Hardness and approximation of multiple sequence alignment with column score
Absent subsequences in words
On recognising words that are squares for the shuffle product
New Error Tolerant Method for Search of Long Repeats in DNA Sequences
Finding shuffle words that represent optimal scheduling of shared memory access
Hybridizations of metaheuristics with branch \& bound derivates
Restricted common superstring and restricted common supersequence
A multiobjective optimization algorithm for the weighted LCS
A new practical linear space algorithm for the longest common subsequence problem
Parameterized Complexity and Approximability of the SLCS Problem
Constrained LCS: Hardness and Approximation
On the Longest Common Parameterized Subsequence
A common basis for similarity measures involving two strings†
The constrained shortest common supersequence problem
Similarity measures for sets of strings^†
Variants of constrained longest common subsequence
On the parameterized complexity of the repetition free longest common subsequence problem
APPLICATION-SPECIFIC ARRAY PROCESSORS FOR THE LONGEST COMMON SUBSEQUENCE PROBLEM OF THREE SEQUENCES ∗ †
Fast algorithms for computing the constrained LCS of run-length encoded strings
Approximability of constrained LCS
A hyper-heuristic for the longest common subsequence problem
Charge and reduce: A fixed-parameter algorithm for string-to-string correction
Parameterized complexity and approximability of the longest compatible sequence problem
On the approximation of shortest common supersequences and longest common subsequences
scientific article; zbMATH DE number 809154 (Why is no real title available?)
Efficient polynomial-time algorithms for the constrained LCS problem with strings exclusion
On the generalized constrained longest common subsequence problems
Scattered Factor-Universality of Words
On the complexity of approximating the independent set problem (extended abstract)
Longest common subsequences
Constrained sequence analysis algorithms in computational biology
Graph logics with rational relations: the role of word combinatorics
Concordance and consensus
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
Approximate periods of strings
Combined super-/substring and super-/subsequence problems
Absent Subsequences in Words
Nearly \(k\)-universal words -- investigating a part of Simon's congruence
scientific article; zbMATH DE number 7758340 (Why is no real title available?)
Algorithms and complexity on indexing founder graphs
Longest Common Subsequence with Gap Constraints
String Covering: A Survey
A policy-based learning beam search for combinatorial optimization
Subsequences in bounded ranges: matching and analysis problems
Existential Definability over the Subword Ordering
Combinatorial algorithms for subsequence matching: a survey

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)