On the parameterized complexity of the repetition free longest common subsequence problem
DOI10.1016/J.IPL.2011.12.009zbMATH Open1237.68094OpenAlexW2055835487MaRDI QIDQ413298FDOQ413298
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
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
algorithmslongest common subsequenceparameterized complexitycombinatorial problemsrepetition free longest common subsequence
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)
Cites Work
- On problems without polynomial kernels
- Faster Algebraic Algorithms for Path and Packing Problems
- Finding and counting vertex-colored subtrees
- Limits and Applications of Group Algebras for Parameterized Problems
- Title not available (Why is that?)
- Finding paths of length \(k\) in \(O^{*}(2^k)\) time
- Infeasibility of instance compression and succinct PCPs for NP
- Variants of constrained longest common subsequence
- Repetition-free longest common subsequence
- Title not available (Why is that?)
- The Complexity of Some Problems on Subsequences and Supersequences
- A simple algorithm for the constrained sequence problems
- Kernel Bounds for Disjoint Cycles and Disjoint Paths
- On the Approximation of Shortest Common Supersequences and Longest Common Subsequences
Cited In (16)
- A Polyhedral Investigation of the LCS Problem and a Repetition-Free Variant
- Comparing incomplete sequences via longest common subsequence
- A\textsuperscript{*}-based compilation of relaxed decision diagrams for the longest common subsequence problem
- Parameterized complexity and approximability of the longest compatible sequence problem
- Repetition-free longest common subsequence
- Solving longest common subsequence problems via a transformation to the maximum clique problem
- On the use of decision diagrams for finding repetition-free longest common subsequences
- Repetition-free longest common subsequence of random sequences
- Repetition-free longest common subsequence
- Listing Center Strings Under the Edit Distance Metric
- Exact algorithms for the repetition-bounded longest common subsequence problem
- Better heuristic algorithms for the repetition free LCS and other variants
- A hybrid genetic algorithm for the repetition free longest common subsequence problem
- Algorithms for Computing the Longest Parameterized Common Subsequence
- On the Longest Common Parameterized Subsequence
- Fixed-parameter algorithms for scaffold filling
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)
