Parameterized complexity and approximability of the longest compatible sequence problem

DOI10.1016/j.disopt.2010.08.003zbMath1248.90066OpenAlexW2027343828MaRDI 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 comparisonparameterized complexitylongest common subsequencelongest compatible sequence

Mathematics Subject Classification ID

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

Related Items (4)

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

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

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