Parameterized complexity and approximability of the longest compatible sequence problem
type: Item
instance of: scholarly article
title: Parameterized complexity and approximability of the longest compatible sequence problem
zbMATH Open document ID: 1248.90066
published in: Discrete Optimization
publication date: 2012-10-16T00:00:00Z
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C60
zbMATH DE Number: 6094032
zbMATH Keywords: parameterized complexity
zbMATH Keywords: sequence comparison
zbMATH Keywords: longest common subsequence
zbMATH Keywords: longest compatible sequence
author: Sylvain Guillemot
MaRDI profile type: Publication
full work available at URL: j.disopt.2010.08.003
OpenAlex ID: W2027343828
cites work: The Complexity of Some Problems on Subsequences and Supersequences
cites work: Q4393480
cites work: Q5710169
cites work: Parametrized complexity theory.
cites work: Analogs & duals of the MAST problem for sequences & trees
cites work: Q5471630
cites work: The Mathematics of Voting and Elections: A Hands-On Approach
cites work: Beyond NP-completeness for problems of bounded width: hardness for the W hierarchy (extended abstract)
cites work: The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs
cites work: The parameterized complexity of sequence alignment and consensus
cites work: Packing directed circuits fractionally
cites work: Approximating minimum feedback sets and multicuts in directed graphs
cites work: Q3549698
cites work: On the parameterized complexity of short computation and factorization
cites work: On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
cites work: Q4544433
DOI: 10.1016/J.DISOPT.2010.08.003
Recommended article: On the parameterized complexity of the repetition free longest common subsequence problem
Recommended article: Q4918894
Recommended article: On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
Recommended article: On the longest common parameterized subsequence
Recommended article: On the Longest Common Parameterized Subsequence
Recommended article: Lower Bounds and Parameterized Approach for Longest Common Subsequence
Recommended article: Algorithms for Computing the Longest Parameterized Common Subsequence
Recommended article: Q6098785
Recommended article: Exact algorithms for the repetition-bounded longest common subsequence problem
Recommended article: The parameterized complexity of sequence alignment and consensus
description: scientific article; zbMATH DE number 6094032