The Complexity of Some Problems on Subsequences and Supersequences
From MaRDI portal
Publication:4147591
DOI10.1145/322063.322075zbMath0371.68018OpenAlexW2040176884WikidataQ56171966 ScholiaQ56171966MaRDI QIDQ4147591
Publication date: 1978
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/322063.322075
Related Items (only showing first 100 items - show all)
A common basis for similarity measures involving two strings† ⋮ Similarity measures for sets of strings† ⋮ Scattered Factor-Universality of Words ⋮ Longest common subsequences ⋮ Absent Subsequences in Words ⋮ Algorithms and complexity on indexing founder graphs ⋮ Constrained LCS: Hardness and Approximation ⋮ On the Longest Common Parameterized Subsequence ⋮ 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 ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the approximation of shortest common supersequences and longest common subsequences ⋮ 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 ⋮ Nearly \(k\)-universal words -- investigating a part of Simon's congruence ⋮ Approximate periods of strings ⋮ Unnamed Item ⋮ Graph Logics with Rational Relations ⋮ On the complexity of approximating the independent set problem ⋮ APPLICATION-SPECIFIC ARRAY PROCESSORS FOR THE LONGEST COMMON SUBSEQUENCE PROBLEM OF THREE SEQUENCES ∗ † ⋮ On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems ⋮ Beam search for the longest common subsequence problem ⋮ Consensus supertrees: The synthesis of rooted trees containing overlapping sets of labeled leaves ⋮ A multiobjective optimization algorithm for the weighted LCS ⋮ Dynamic programming algorithms for the mosaic longest common subsequence problem ⋮ Efficient algorithms for finding interleaving relationship between sequences ⋮ On the longest common rigid subsequence problem ⋮ Constrained string editing ⋮ Searching subsequences ⋮ RNA multiple structural alignment with longest common subsequences ⋮ A simple algorithm for the constrained sequence problems ⋮ Novel evolutionary models and applications to sequence alignment problems ⋮ The parameterized complexity of sequence alignment and consensus ⋮ A beam search for the shortest common supersequence problem guided by an approximate expected length calculation ⋮ Longest common subsequence problem for unoriented and cyclic strings ⋮ Optimality regions and fluctuations for Bernoulli last passage models ⋮ Combined super-/substring and super-/subsequence problems ⋮ The consensus string problem for a metric is NP-complete ⋮ Solving longest common subsequence problems via a transformation to the maximum clique problem ⋮ A hardness result and new algorithm for the longest common palindromic subsequence problem ⋮ Improved heuristics and a genetic algorithm for finding short supersequences ⋮ The constrained shortest common supersequence problem ⋮ Hybridizations of Metaheuristics With Branch & Bound Derivates ⋮ Parameterized Complexity and Approximability of the SLCS Problem ⋮ Variants of constrained longest common subsequence ⋮ Hardness and approximation of multiple sequence alignment with column score ⋮ A branch-and-bound framework for unsupervised common event discovery ⋮ 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 ⋮ Fast algorithms for computing the constrained LCS of run-length encoded strings ⋮ The string merging problem ⋮ Absent subsequences in words ⋮ The shortest common supersequence problem over binary alphabet is NP- complete ⋮ Sequence matching with binary codes ⋮ Approximability of constrained LCS ⋮ A hyper-heuristic for the longest common subsequence problem ⋮ On recognising words that are squares for the shuffle product ⋮ FACC: a novel finite automaton based on cloud computing for the multiple longest common subsequences search ⋮ Charge and reduce: A fixed-parameter algorithm for string-to-string correction ⋮ Parameterized complexity and approximability of the longest compatible sequence problem ⋮ The multi-spreader crane scheduling problem: partitions and supersequences ⋮ On the complexity of finding common approximate substrings. ⋮ An efficient algorithm for LCS problem between two arbitrary sequences ⋮ 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 ⋮ An \(A^\ast\) search algorithm for the constrained longest common subsequence problem ⋮ Algorithms for computing variants of the longest common subsequence problem ⋮ On the inadequacy of tournament algorithms for the \(N\)-SCS problem ⋮ Multiple genome rearrangement by swaps and by element duplications ⋮ Efficient polynomial-time algorithms for the constrained LCS problem with strings exclusion ⋮ On the generalized constrained longest common subsequence problems ⋮ On the complexity of approximating the independent set problem ⋮ Consistent subsequences and supersequences ⋮ On the approximation of longest common nonsupersequences and shortest common nonsubsequences ⋮ Generalized random shapelet forests ⋮ On searching and indexing sequences of temporal intervals ⋮ Comparing bacterial genomes from linear orders of patterns ⋮ 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 ⋮ Feasibility recovery for the unit-capacity constrained permutation problem ⋮ Consensus sequences based on plurality rule ⋮ The unit-capacity constrained permutation problem ⋮ On the complexity of learning strings and sequences ⋮ Constrained sequence analysis algorithms in computational biology ⋮ Minimum cost multi-product flow lines ⋮ New efficient algorithms for the LCS and constrained LCS problems ⋮ The complexity of flood filling games ⋮ An improved algorithm for the longest common subsequence problem ⋮ The shortest common nonsubsequence problem is NP-complete ⋮ Concordance and consensus ⋮ About the design of oligo-chips ⋮ Finite automata based algorithms on subsequences and supersequences of degenerate strings ⋮ Scheduling tasks on a flexible manufacturing machine to minimize tool change delays ⋮ Finding common structured patterns in linear graphs
This page was built for publication: The Complexity of Some Problems on Subsequences and Supersequences
