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

DOI10.1016/J.IPL.2011.12.009MaRDI QIDQ413298zbMATHOpenAlexFDO

Authors Guillaume Blin, Paola Bonizzoni, Riccardo Dondi, Florian Sikora

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

algorithmslongest common subsequenceparameterized complexitycombinatorial problemsrepetition free longest common subsequence

Mathematics Subject Classification ID

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

Recommendations

• On the longest common parameterized subsequence
• On the Longest Common Parameterized Subsequence
• Exact algorithms for the repetition-bounded longest common subsequence problem
• scientific article; zbMATH DE number 6161102
• Lower Bounds and Parameterized Approach for Longest Common Subsequence
• Exact algorithms for the bounded repetition longest common subsequence problem
• A branch-and-cut approach to the repetition-free longest common subsequence problem
• On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
• Algorithms for Computing the Longest Parameterized Common Subsequence
• Parameterized complexity and approximability of the longest compatible sequence problem

Cites work

• scientific article; zbMATH DE number 1507224 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A simple algorithm for the constrained sequence problems
• Faster Algebraic Algorithms for Path and Packing Problems
• Finding and counting vertex-colored subtrees
• Finding paths of length \(k\) in \(O^{*}(2^k)\) time
• Infeasibility of instance compression and succinct PCPs for NP
• Kernel Bounds for Disjoint Cycles and Disjoint Paths
• Limits and Applications of Group Algebras for Parameterized Problems
• On problems without polynomial kernels
• On the Approximation of Shortest Common Supersequences and Longest Common Subsequences
• Repetition-free longest common subsequence
• The Complexity of Some Problems on Subsequences and Supersequences
• Variants of constrained longest common subsequence

Cited in

(17)

• Listing center strings under the edit distance metric
• Repetition-free longest common subsequence
• A\textsuperscript{*}-based compilation of relaxed decision diagrams for the longest common subsequence problem
• A hybrid genetic algorithm for the repetition free longest common subsequence problem
• Fixed-parameter algorithms for scaffold filling
• Exact algorithms for the bounded repetition longest common subsequence problem
• Solving longest common subsequence problems via a transformation to the maximum clique problem
• Exact algorithms for the repetition-bounded longest common subsequence problem
• Better heuristic algorithms for the repetition free LCS and other variants
• On the use of decision diagrams for finding repetition-free longest common subsequences
• Parameterized complexity and approximability of the longest compatible sequence problem
• Repetition-free longest common subsequence
• A Polyhedral Investigation of the LCS Problem and a Repetition-Free Variant
• Comparing incomplete sequences via longest common subsequence
• Algorithms for Computing the Longest Parameterized Common Subsequence
• On the Longest Common Parameterized Subsequence
• Repetition-free longest common subsequence of random sequences

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

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