The constrained shortest common supersequence problem

DOI10.1016/j.jda.2013.03.004zbMath1334.68316OpenAlexW2092175862MaRDI QIDQ396654

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)

Related Items (1)

The multi-spreader crane scheduling problem: partitions and supersequences

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Variants of constrained longest common subsequence
• New efficient algorithms for the LCS and constrained LCS problems
• The constrained longest common subsequence problem
• The shortest common supersequence problem over binary alphabet is NP- complete
• Some APX-completeness results for cubic graphs
• A simple algorithm for the constrained sequence problems
• A branch-and-cut approach to the repetition-free longest common subsequence problem
• Restricted Common Superstring and Restricted Common Supersequence
• The Complexity of Some Problems on Subsequences and Supersequences
• On the Approximation of Shortest Common Supersequences and Longest Common Subsequences
• ALGORITHMS FOR THE CONSTRAINED LONGEST COMMON SUBSEQUENCE PROBLEMS
• Repetition-free longest common subsequence

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