Parameterized complexity and approximability of the longest compatible sequence problem
From MaRDI portal
Publication:456697
DOI10.1016/j.disopt.2010.08.003zbMath1248.90066OpenAlexW2027343828MaRDI QIDQ456697
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
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