Parameterized complexity and approximability of the longest compatible sequence problem

DOI10.1016/J.DISOPT.2010.08.003zbMATH Open1248.90066OpenAlexW2027343828MaRDI QIDQ456697FDOQ456697

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)

Cites Work

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

Cited In (6)

• On the parameterized complexity of the repetition free longest common subsequence problem
• Complexity and approximation of the longest vector sum problem
• Designing FPT Algorithms for Cut Problems Using Randomized Contractions
• On the space and circuit complexity of parameterized problems: classes and completeness
• Synchronizing words and monoid factorization, yielding a new parameterized complexity class?
• Synchronizing series-parallel deterministic finite automata with loops and related problems

Recommendations

• On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems 👍 👎
• On the parameterized complexity of the repetition free longest common subsequence problem 👍 👎
• On the longest common parameterized subsequence 👍 👎
• Exact algorithms for the repetition-bounded longest common subsequence problem 👍 👎
• Algorithms for Computing the Longest Parameterized Common Subsequence 👍 👎
• On the Longest Common Parameterized Subsequence 👍 👎
• Lower Bounds and Parameterized Approach for Longest Common Subsequence 👍 👎
• The parameterized complexity of sequence alignment and consensus 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎

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)