Comparing incomplete sequences via longest common subsequence

DOI10.1016/j.tcs.2019.09.022zbMath1435.68396OpenAlexW2974309155MaRDI QIDQ2333802

Italo Zoppis, Riccardo Dondi, Mauro Castelli, Giancarlo Mauri

Publication date: 13 November 2019

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2019.09.022

zbMATH Keywords

computational complexityapproximation algorithmsstring algorithmsfixed-parameter algorithmslongest common subsequence

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Algorithms on strings (68W32)

Cites Work

• Unnamed Item
• Unnamed Item
• Variants of constrained longest common subsequence
• On the parameterized complexity of the repetition free longest common subsequence problem
• The constrained longest common subsequence problem
• Some APX-completeness results for cubic graphs
• A simple algorithm for the constrained sequence problems
• Fixed-parameter algorithms for scaffold filling
• A branch-and-cut approach to the repetition-free longest common subsequence problem
• Constrained LCS: Hardness and Approximation
• Color-coding
• Genomic Scaffold Filling: A Progress Report
• On the Approximation of Shortest Common Supersequences and Longest Common Subsequences
• The longest filled common subsequence problem
• ALGORITHMS FOR THE CONSTRAINED LONGEST COMMON SUBSEQUENCE PROBLEMS
• Repetition-free longest common subsequence

This page was built for publication: Comparing incomplete sequences via longest common subsequence