Longest common subsequence problem for unoriented and cyclic strings
type: Item
instance of: scholarly article
title: Longest common subsequence problem for unoriented and cyclic strings
zbMATH Open document ID: 1118.68074
author: François Nicolas
author: Eric Rivals
published in: Theoretical Computer Science
publication date: 2007-02-26T00:00:00Z
full work available at URL: NR-TCS-1006.pdf
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 92D20
zbMATH DE Number: 5129779
zbMATH Keywords: longest common subsequence
zbMATH Keywords: LCS
zbMATH Keywords: cyclic string
zbMATH Keywords: sequence comparison
zbMATH Keywords: pattern recognition
zbMATH Keywords: graph
zbMATH Keywords: hypergraph
zbMATH Keywords: maximum stable set
zbMATH Keywords: maximum independent set
zbMATH Keywords: approximation
zbMATH Keywords: parameterized complexity
zbMATH Keywords: NP-hard
zbMATH Keywords: W[1]-hard
MaRDI profile type: Publication
OpenAlex ID: W1983717807
cites work: Q4509227
cites work: Algorithms on Strings, Trees and Sequences
cites work: Algorithms for the Longest Common Subsequence Problem
cites work: A faster algorithm computing string edit distances
cites work: An \(O(ND)\) difference algorithm and its variations
cites work: A Subquadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices
cites work: On a cyclic string-to-string correction problem
cites work: All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings
cites work: Incremental String Comparison
cites work: The string merging problem
cites work: The Complexity of Some Problems on Subsequences and Supersequences
cites work: On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
cites work: On the Approximation of Shortest Common Supersequences and Longest Common Subsequences
cites work: The parameterized complexity of sequence alignment and consensus
cites work: The shortest common supersequence problem over binary alphabet is NP- complete
cites work: More on the complexity of common superstring and supersequence problems
cites work: Introduction to algorithms
cites work: Q4393480
cites work: Approximations of Weighted Independent Set and Hereditary Subset Problems
cites work: Approximating maximum independent sets by excluding subgraphs
cites work: Clique is hard to approximate within \(n^{1-\epsilon}\)
cites work: Towards optimal lower bounds for clique and chromatic number.
cites work: Q4341774
cites work: Q4258216
cites work: Approximate coloring of uniform hypergraphs
DOI: 10.1016/J.TCS.2006.10.002
description: scientific article; zbMATH DE number 5129779