On the parameterized complexity of the repetition free longest common subsequence problem
From MaRDI portal
Publication:413298
DOI10.1016/j.ipl.2011.12.009zbMath1237.68094MaRDI 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
algorithms; combinatorial problems; parameterized complexity; longest common subsequence; repetition free longest common subsequence
68Q25: Analysis of algorithms and problem complexity
68R05: Combinatorics in computer science
92D20: Protein sequences, DNA sequences
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
Listing Center Strings Under the Edit Distance Metric, Repetition-free longest common subsequence of random sequences, Exact algorithms for the repetition-bounded longest common subsequence problem, Comparing incomplete sequences via longest common subsequence, A hybrid genetic algorithm for the repetition free longest common subsequence problem, Fixed-parameter algorithms for scaffold filling, Solving longest common subsequence problems via a transformation to the maximum clique problem
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
