On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
From MaRDI portal
Publication:1877706
DOI10.1016/S0022-0000(03)00078-3zbMath1092.68049MaRDI QIDQ1877706
Publication date: 19 August 2004
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Parameterized complexity; Shortest common supersequence; Multiple sequence alignment; Longest common subsequence
68Q25: Analysis of algorithms and problem complexity
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Compact Flow Diagrams for State Sequences, Unnamed Item, Unnamed Item, Unnamed Item, A Parameterized Perspective on Attacking and Defending Elections, Sum-of-Products with Default Values: Algorithms and Complexity Results, Learning Bayesian Networks Under Sparsity Constraints: A Parameterized Complexity Analysis, Listing Center Strings Under the Edit Distance Metric, Minimum reload cost graph factors, The complexity of tree partitioning, A parameterized study of maximum generalized pattern matching problems, On the parameterised complexity of string morphism problems, Model counting for CNF formulas of bounded modular treewidth, Satisfiability of acyclic and almost acyclic CNF formulas, Variants of constrained longest common subsequence, Editing graphs to satisfy degree constraints: a parameterized approach, Parameterized complexity and approximability of the longest compatible sequence problem, The parameterized complexity of \(k\)-flip local search for SAT and MAX SAT, Parameterized complexity of three edge contraction problems with degree constraints, On finding optimal polytrees, Parameterizing by the number of numbers, Longest common subsequence problem for unoriented and cyclic strings, On parameterized complexity of the multi-MCS problem, The many facets of upper domination, Parameterized complexity results for general factors in bipartite graphs with an application to constraint programming, Taxi-sharing: parameterized complexity and approximability of the dial-a-ride problem with money as an incentive, Computing the similarity of two sequences with nested arc annotations, Metric dimension parameterized by treewidth, Parameterized complexity of two-interval pattern problem, Length-bounded cuts: proper interval graphs and structural parameters, Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity, On the tractability of optimization problems on \(H\)-graphs, The multi-spreader crane scheduling problem: partitions and supersequences, On structural parameterizations of the bounded-degree vertex deletion problem, The complexity landscape of decompositional parameters for ILP: programs with few global variables and constraints, Mim-width. II. The feedback vertex set problem, Subset feedback vertex set on graphs of bounded independent set size, Backdoors to planning, Mim-width. III. Graph powers and generalized distance domination problems, Tractability and hardness of flood-filling games on trees, A complete parameterized complexity analysis of bounded planning, Parameterized complexity of the MinCCA problem on graphs of bounded decomposability, Parameterized complexity of secluded connectivity problems, The parameterized complexity of stabbing rectangles, Tractable cases of the extended global cardinality constraint, Parameterized domination in circle graphs, On the computational hardness based on linear fpt-reductions, Hardness results for the center and median string problems under the weighted and unweighted edit distances, Reconfiguration of cliques in a graph, Group activity selection with few agent types, Algorithmic Aspects of Upper Domination: A Parameterised Perspective, Split-Plot Designs for Robotic Serial Dilution Assays, Backdoors to Satisfaction, FPT Suspects and Tough Customers: Open Problems of Downey and Fellows, On Directed Steiner Trees with Multiple Roots, Parameterized Complexity and Approximability of the SLCS Problem, The Parameterized Complexity of k-Flip Local Search for SAT and MAX SAT
Cites Work
- Unnamed Item
- The shortest common supersequence problem over binary alphabet is NP- complete
- The parameterized complexity of sequence alignment and consensus
- Bounds on the Complexity of the Longest Common Subsequence Problem
- The Complexity of Some Problems on Subsequences and Supersequences
- Algorithms for the longest common subsequence problem for multiple strings based on geometric maxima
