The constrained shortest common supersequence problem

DOI10.1016/J.JDA.2013.03.004MaRDI QIDQ396654zbMATH OpenOpenAlexFDO

Authors Riccardo Dondi

Publication date 13 August 2014

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jda.2013.03.004

zbMATH Keywords

computational complexityapproximation algorithmsfixed-parameter algorithmsshortest common supersequence

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Algorithms on strings (68W32)

Recommendations

• The constrained longest common subsequence problem
• scientific article; zbMATH DE number 827942
• scientific article; zbMATH DE number 1859299
• Approximation algorithms for the shortest common superstring problem
• ALGORITHMS FOR THE CONSTRAINED LONGEST COMMON SUBSEQUENCE PROBLEMS
• On the approximation of shortest common supersequences and longest common subsequences
• On the Approximation of Shortest Common Supersequences and Longest Common Subsequences
• Reoptimization of the shortest common superstring problem
• On solving a generalized constrained longest common subsequence problem

Cites work

• scientific article; zbMATH DE number 3599517 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A branch-and-cut approach to the repetition-free longest common subsequence problem
• A simple algorithm for the constrained sequence problems
• ALGORITHMS FOR THE CONSTRAINED LONGEST COMMON SUBSEQUENCE PROBLEMS
• New efficient algorithms for the LCS and constrained LCS problems
• On the Approximation of Shortest Common Supersequences and Longest Common Subsequences
• Repetition-free longest common subsequence
• Restricted common superstring and restricted common supersequence
• Some APX-completeness results for cubic graphs
• The Complexity of Some Problems on Subsequences and Supersequences
• The constrained longest common subsequence problem
• The shortest common supersequence problem over binary alphabet is NP- complete
• Variants of constrained longest common subsequence

Cited in

(6)

• scientific article; zbMATH DE number 827942 (Why is no real title available?)
• The multi-spreader crane scheduling problem: partitions and supersequences
• Restricted common superstring and restricted common supersequence
• Combined super-/substring and super-/subsequence problems
• The shortest common nonsubsequence problem is NP-complete
• An approximate \(A^{\ast}\) algorithm and its application to the SCS problem.

This page was built for publication: The constrained shortest common supersequence problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q396654)