Parameterized complexity and approximability of the longest compatible sequence problem

DOI10.1016/j.disopt.2010.08.003zbMath1248.90066MaRDI QIDQ456697

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

sequence comparison; parameterized complexity; longest common subsequence; longest compatible sequence

Mathematics Subject Classification ID

90C60: Abstract computational complexity for mathematical programming problems

90C27: Combinatorial optimization

Related Items

Synchronizing series-parallel deterministic finite automata with loops and related problems, Synchronizing words and monoid factorization, yielding a new parameterized complexity class?, On the space and circuit complexity of parameterized problems: classes and completeness, Designing FPT Algorithms for Cut Problems Using Randomized Contractions

Cites Work

• Unnamed Item
• 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
• The Mathematics of Voting and Elections: A Hands-On Approach
• Analogs & duals of the MAST problem for sequences & trees