Parameterized Complexity and Approximability of the SLCS Problem

DOI10.1007/978-3-540-79723-4_12MaRDI QIDQ3503583zbMATH OpenOpenAlexFDO

Authors Sylvain Guillemot

Publication date 5 June 2008

Published in Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-79723-4_12

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Combinatorics on words (68R15)

Recommendations

• Parameterized complexity and approximability of the longest compatible sequence problem
• On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
• The parameterized complexity of sequence alignment and consensus
• On the Longest Common Parameterized Subsequence
• On the longest common parameterized subsequence

Cites work

• Analogs & duals of the MAST problem for sequences & trees
• Approximating minimum feedback sets and multicuts in directed graphs
• Beyond NP-completeness for problems of bounded width: hardness for the W hierarchy (extended abstract)
• scientific article; zbMATH DE number 5485529 (Why is no real title available?)
• scientific article; zbMATH DE number 1507224 (Why is no real title available?)
• scientific article; zbMATH DE number 1775632 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• On the parameterized complexity of short computation and factorization
• On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
• Packing directed circuits fractionally
• Parametrized complexity theory.
• The Complexity of Some Problems on Subsequences and Supersequences
• The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs
• The Mathematics of Voting and Elections: A Hands-On Approach
• The parameterized complexity of sequence alignment and consensus

Cited in

(3)

• On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
• Iterative Compression for Exactly Solving NP-Hard Minimization Problems
• Complexity issues in vertex-colored graph pattern matching

This page was built for publication: Parameterized Complexity and Approximability of the SLCS Problem

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