scientific article; zbMATH DE number 6161102

MaRDI QIDQ4918894zbMATH OpenFDO

Authors Anna Gorbenko, Vladimir Popov

Publication date 7 May 2013

Full work available at URL http://www.m-hikari.com/ams/ams-2012/ams-57-60-2012/index.html

zbMATH Keywords

logical modelsNP-completenessparameterized pattern matching

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Algorithms on strings (68W32)

Cited in

(13)

• Computing the longest topological common subsequence of a symbol-wise totally ordered directed acyclic graph and a sequence
• The shortest common nonsubsequence problem is NP-complete
• The longest common subsequence problem for sequences with nested arc annotations.
• Anytime algorithms for the longest common palindromic subsequence problem
• scientific article; zbMATH DE number 1615278 (Why is no real title available?)
• The Constrained Longest Common Subsequence Problem for Degenerate Strings
• On the Longest Common Parameterized Subsequence
• On the parameterized complexity of the repetition free longest common subsequence problem
• Parameterized complexity and approximability of the longest compatible sequence problem
• The longest filled common subsequence problem
• Longest Common Subsequences in Permutations and Maximum Cliques in Circle Graphs
• Dynamic programming algorithms for the mosaic longest common subsequence problem
• Thermodynamical approach to the longest common subsequence problem

This page was built for publication:

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