Parameterized Complexity and Approximability of the SLCS Problem

DOI10.1007/978-3-540-79723-4_12zbMath1142.68372OpenAlexW1920445071MaRDI QIDQ3503583

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

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

Related Items

Complexity issues in vertex-colored graph pattern matching ⋮ Iterative Compression for Exactly Solving NP-Hard Minimization Problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The parameterized complexity of sequence alignment and consensus
• Approximating minimum feedback sets and multicuts in directed graphs
• On the parameterized complexity of short computation and factorization
• The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs
• On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
• Packing directed circuits fractionally
• Parametrized complexity theory.
• Beyond NP-completeness for problems of bounded width (extended abstract)
• The Complexity of Some Problems on Subsequences and Supersequences
• Analogs & duals of the MAST problem for sequences & trees
• The Mathematics of Voting and Elections: A Hands-On Approach

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