Variants of constrained longest common subsequence

DOI10.1016/j.ipl.2010.07.015zbMath1234.68472arXiv0912.0368OpenAlexW2038282261MaRDI QIDQ407588

Gianluca Della Vedova, Paola Bonizzoni, Yuri Pirola, Riccardo Dondi

Publication date: 27 March 2012

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0912.0368

zbMATH Keywords

fixed-parameter tractabilitylongest common subsequenceconstrained longest common subsequence

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithms on strings (68W32)

Related Items (12)

Repetition-free longest common subsequence of random sequences ⋮ Parameterized tractability of the maximum-duo preservation string mapping problem ⋮ Solving longest common subsequence problems via a transformation to the maximum clique problem ⋮ The constrained shortest common supersequence problem ⋮ On the parameterized complexity of the repetition free longest common subsequence problem ⋮ Exact algorithms for the repetition-bounded longest common subsequence problem ⋮ Doubly-constrained LCS and hybrid-constrained LCS problems revisited ⋮ Approximability of constrained LCS ⋮ A hybrid genetic algorithm for the repetition free longest common subsequence problem ⋮ Maximum disjoint paths on edge-colored graphs: approximability and tractability ⋮ Fixed-parameter algorithms for scaffold filling ⋮ Comparing incomplete sequences via longest common subsequence

Cites Work

• Unnamed Item
• Unnamed Item
• The constrained longest common subsequence problem
• Improving the worst-case performance of the Hunt-Szymanski strategy for the longest common subsequence of two strings
• The longest common subsequence problem revisited
• The shortest common supersequence problem over binary alphabet is NP- complete
• Fast linear-space computations of longest common subsequences
• On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
• A simple algorithm for the constrained sequence problems
• The Spatial Complexity of Oblivious k-Probe Hash Functions
• Constrained LCS: Hardness and Approximation
• The Complexity of Some Problems on Subsequences and Supersequences
• Color-coding
• On the Approximation of Shortest Common Supersequences and Longest Common Subsequences
• A Polyhedral Investigation of the LCS Problem and a Repetition-Free Variant
• DICTIONARY LOOK-UP WITHIN SMALL EDIT DISTANCE
• Repetition-free longest common subsequence

This page was built for publication: Variants of constrained longest common subsequence