On the parameterized complexity of the repetition free longest common subsequence problem

DOI10.1016/j.ipl.2011.12.009zbMath1237.68094OpenAlexW2055835487MaRDI QIDQ413298

Paola Bonizzoni, Riccardo Dondi, Florian Sikora, Guillaume Blin

Publication date: 4 May 2012

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

Full work available at URL: https://doi.org/10.1016/j.ipl.2011.12.009

zbMATH Keywords

algorithmscombinatorial problemsparameterized complexitylongest common subsequencerepetition free longest common subsequence

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Protein sequences, DNA sequences (92D20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (7)

Repetition-free longest common subsequence of random sequences ⋮ Solving longest common subsequence problems via a transformation to the maximum clique problem ⋮ Exact algorithms for the repetition-bounded longest common subsequence problem ⋮ A hybrid genetic algorithm for the repetition free longest common subsequence problem ⋮ Listing Center Strings Under the Edit Distance Metric ⋮ Fixed-parameter algorithms for scaffold filling ⋮ Comparing incomplete sequences via longest common subsequence

Cites Work

• Unnamed Item
• Unnamed Item
• Variants of constrained longest common subsequence
• Infeasibility of instance compression and succinct PCPs for NP
• Finding paths of length \(k\) in \(O^{*}(2^k)\) time
• On problems without polynomial kernels
• A simple algorithm for the constrained sequence problems
• Faster Algebraic Algorithms for Path and Packing Problems
• Finding and Counting Vertex-Colored Subtrees
• Limits and Applications of Group Algebras for Parameterized Problems
• Kernel Bounds for Disjoint Cycles and Disjoint Paths
• The Complexity of Some Problems on Subsequences and Supersequences
• On the Approximation of Shortest Common Supersequences and Longest Common Subsequences
• Repetition-free longest common subsequence

This page was built for publication: On the parameterized complexity of the repetition free longest common subsequence problem