Longest common subsequence problem for unoriented and cyclic strings

DOI10.1016/j.tcs.2006.10.002zbMath1118.68074OpenAlexW1983717807MaRDI QIDQ868937

Eric Rivals, François Nicolas

Publication date: 26 February 2007

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://hal-lirmm.ccsd.cnrs.fr/lirmm-00120152/file/NR-TCS-1006.pdf

zbMATH Keywords

graphhypergraphpattern recognitionapproximationNP-hardmaximum independent setsequence comparisonparameterized complexitylongest common subsequencemaximum stable setLCScyclic stringW[1-hard]

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Protein sequences, DNA sequences (92D20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

Cyclic longest common subsequence ⋮ Exploiting a hypergraph model for finding Golomb rulers

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On a cyclic string-to-string correction problem
• An \(O(ND)\) difference algorithm and its variations
• A faster algorithm computing string edit distances
• The string merging problem
• The shortest common supersequence problem over binary alphabet is NP- complete
• Approximating maximum independent sets by excluding subgraphs
• More on the complexity of common superstring and supersequence problems
• The parameterized complexity of sequence alignment and consensus
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Towards optimal lower bounds for clique and chromatic number.
• On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
• The Complexity of Some Problems on Subsequences and Supersequences
• Algorithms for the Longest Common Subsequence Problem
• All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings
• Algorithms on Strings, Trees and Sequences
• Incremental String Comparison
• A Subquadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices
• Approximations of Weighted Independent Set and Hereditary Subset Problems
• Approximate coloring of uniform hypergraphs
• On the Approximation of Shortest Common Supersequences and Longest Common Subsequences