On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems

DOI10.1016/S0022-0000(03)00078-3zbMath1092.68049MaRDI QIDQ1877706

Krzysztof Pietrzak

Publication date: 19 August 2004

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

zbMATH Keywords

Parameterized complexityShortest common supersequenceMultiple sequence alignmentLongest common subsequence

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (59)

Length-bounded cuts: proper interval graphs and structural parameters ⋮ A Parameterized Perspective on Attacking and Defending Elections ⋮ Split-Plot Designs for Robotic Serial Dilution Assays ⋮ Computing the similarity of two sequences with nested arc annotations ⋮ Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity ⋮ A parameterized study of maximum generalized pattern matching problems ⋮ On the parameterised complexity of string morphism problems ⋮ Backdoors to Satisfaction ⋮ FPT Suspects and Tough Customers: Open Problems of Downey and Fellows ⋮ On Directed Steiner Trees with Multiple Roots ⋮ Model counting for CNF formulas of bounded modular treewidth ⋮ Sum-of-Products with Default Values: Algorithms and Complexity Results ⋮ Parameterized complexity of the MinCCA problem on graphs of bounded decomposability ⋮ Longest common subsequence problem for unoriented and cyclic strings ⋮ Parameterized complexity of secluded connectivity problems ⋮ Compact Flow Diagrams for State Sequences ⋮ Satisfiability of acyclic and almost acyclic CNF formulas ⋮ Learning Bayesian Networks Under Sparsity Constraints: A Parameterized Complexity Analysis ⋮ Parameterized Complexity and Approximability of the SLCS Problem ⋮ Variants of constrained longest common subsequence ⋮ Editing graphs to satisfy degree constraints: a parameterized approach ⋮ On the tractability of optimization problems on \(H\)-graphs ⋮ The parameterized complexity of stabbing rectangles ⋮ Tractable cases of the extended global cardinality constraint ⋮ An FPT algorithm for node-disjoint subtrees problems parameterized by treewidth ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The many facets of upper domination ⋮ Reconfiguration of cliques in a graph ⋮ Group activity selection with few agent types ⋮ Parameterized domination in circle graphs ⋮ Parameterized complexity and approximability of the longest compatible sequence problem ⋮ The parameterized complexity of \(k\)-flip local search for SAT and MAX SAT ⋮ The multi-spreader crane scheduling problem: partitions and supersequences ⋮ Parameterized complexity of three edge contraction problems with degree constraints ⋮ On structural parameterizations of the bounded-degree vertex deletion problem ⋮ On finding optimal polytrees ⋮ The complexity landscape of decompositional parameters for ILP: programs with few global variables and constraints ⋮ Parameterizing by the number of numbers ⋮ Parameterized complexity results for general factors in bipartite graphs with an application to constraint programming ⋮ Listing Center Strings Under the Edit Distance Metric ⋮ Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage ⋮ On the computational hardness based on linear fpt-reductions ⋮ Taxi-sharing: parameterized complexity and approximability of the dial-a-ride problem with money as an incentive ⋮ Mim-width. II. The feedback vertex set problem ⋮ Minimum reload cost graph factors ⋮ Metric dimension parameterized by treewidth ⋮ The complexity of tree partitioning ⋮ Subset feedback vertex set on graphs of bounded independent set size ⋮ On parameterized complexity of the multi-MCS problem ⋮ The Parameterized Complexity of k-Flip Local Search for SAT and MAX SAT ⋮ Algorithmic Aspects of Upper Domination: A Parameterised Perspective ⋮ Parameterized complexity of two-interval pattern problem ⋮ Backdoors to planning ⋮ Hardness results for the center and median string problems under the weighted and unweighted edit distances ⋮ 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

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

This page was built for publication: On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems