The longest filled common subsequence problem

DOI10.4230/LIPICS.CPM.2017.14MaRDI QIDQ5110878zbMATH OpenOpenAlexFDO

Authors Mauro Castelli, Riccardo Dondi, Giancarlo Mauri, Italo Zoppis

Publication date 25 May 2020

Full work available at URL https://doi.org/10.4230/LIPIcs.CPM.2017.14

zbMATH Keywords

approximation algorithmscomputational complexityfixed-parameter algorithmslongest common subsequence

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27) Approximation algorithms (68W25) Algorithms on strings (68W32)

Recommendations

• scientific article; zbMATH DE number 6161488
• The longest common subsequence problem revisited
• scientific article; zbMATH DE number 6161102
• The longest commonly positioned increasing subsequences problem
• The constrained longest common subsequence problem
• Longest common subsequences
• On the longest common parameterized subsequence
• On the Longest Common Parameterized Subsequence
• Combinatorial Pattern Matching
• On the longest common rigid subsequence problem

Cited in

(5)

• The shortest common nonsubsequence problem is NP-complete
• Comparing incomplete sequences via longest common subsequence
• Sketching, streaming, and fine-grained complexity of (weighted) LCS
• The longest run subsequence problem
• Polynomial-time equivalences and refined algorithms for longest common subsequence variants

This page was built for publication: The longest filled common subsequence problem

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