Parameterized complexity and approximability of the longest compatible sequence problem

DOI10.1016/J.DISOPT.2010.08.003MaRDI QIDQ456697zbMATHOpenAlexFDO

Authors Sylvain Guillemot

Publication date 16 October 2012

Published in Discrete Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disopt.2010.08.003

zbMATH Keywords

longest common subsequenceparameterized complexitysequence comparisonlongest compatible sequence

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• On the parameterized complexity of the repetition free longest common subsequence problem
• scientific article; zbMATH DE number 6161102
• On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
• On the longest common parameterized subsequence
• On the Longest Common Parameterized Subsequence
• Lower Bounds and Parameterized Approach for Longest Common Subsequence
• Algorithms for Computing the Longest Parameterized Common Subsequence
• scientific article; zbMATH DE number 7696000
• Exact algorithms for the repetition-bounded longest common subsequence problem
• The parameterized complexity of sequence alignment and consensus

Cites work

• scientific article; zbMATH DE number 5485529 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (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?)
• 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)
• 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.
• Reconstructing phylogenies from gene-content and gene-order data
• The Complexity of Some Problems on Subsequences and Supersequences
• The Mathematics of Voting and Elections: A Hands-On Approach
• The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs
• The parameterized complexity of sequence alignment and consensus

Cited in

(7)

• Synchronizing words and monoid factorization, yielding a new parameterized complexity class?
• Parameterized Complexity and Approximability of the SLCS Problem
• Designing FPT algorithms for cut problems using randomized contractions
• Synchronizing series-parallel deterministic finite automata with loops and related problems
• On the parameterized complexity of the repetition free longest common subsequence problem
• Complexity and approximation of the longest vector sum problem
• On the space and circuit complexity of parameterized problems: classes and completeness

This page was built for publication: Parameterized complexity and approximability of the longest compatible sequence problem

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