Live briefing
Everything about Shortest common supersequence
In computer science, the shortest common supersequence of two sequences X and Y is the shortest sequence which has X and Y as subsequences. This is a problem closely related to the longest common subsequence problem. Given two sequences X = < x1,...,xm > and Y = < y1,...,yn >, a sequence U = < u1,...,uk > is a common supersequence of X and Y if items can be removed from U to produce X and Y. Wikipedia →
🧭 Start here: a 6-step reading path
- Read the overview: Shortest common supersequenceA 5-minute orientation
- Skim a recent paper: An Opposition-Based Learning CRO Algorithm for Solving the Shortest Common Supersequence ProblemInfluential work since 2022
- Read the landmark paper: On the Approximation of Shortest Common Supersequences and Longest Common SubsequencesCited 145 times
- Go sideways: Longest common subsequenceA closely related topic
- Go sideways: Levenshtein distanceA closely related topic
📖 Definitions
No dictionary entry for this exact phrase.
🗂️ The subject at a glance
🏆 Landmark papers (most cited)
On the Approximation of Shortest Common Supersequences and Longest Common Subsequences
On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
A greedy approximation algorithm for constructing shortest common superstrings
The shortest common supersequence problem over binary alphabet is NP-complete
Approximation algorithms for the shortest common superstring problem
A linear-time algorithm for finding approximate shortest common superstrings
The shortest common supersequence problem in a microarray production setting
Chemical reaction optimization for solving shortest common supersequence problem
🆕 Influential since 2022
An Opposition-Based Learning CRO Algorithm for Solving the Shortest Common Supersequence Problem
The tree-child network inference problem for line trees and the shortest common supersequence problem for permutation strings
Phase transition in the computational complexity of the shortest common superstring and genome assembly
📚 Books worth reading
Open Library didn't respond; try again in a moment.
🔗 Related topics
- Longest common subsequence A longest common subsequence (LCS) is the longest subsequence common to all sequences in a set of sequences (often just two sequences). It differs from…
- Levenshtein distance In information theory, linguistics, and computer science, the Levenshtein distance is a string metric for measuring the difference between two sequences…
- Substring In formal language theory and computer science, a substring is a contiguous sequence of characters within a string. For instance, "the best of" is a substring…
- Longest increasing subsequence In computer science, the longest increasing subsequence problem aims to find a subsequence of a given sequence in which the subsequence's elements are…
- Subsequence In mathematics, a subsequence of a given sequence is a sequence that can be derived from the given sequence by deleting some or no elements without changing…
- Stochastic approximation Stochastic approximation methods are a family of iterative methods typically used for root-finding problems or for optimization problems. The recursive…
- Maximum disjoint set In computational geometry, a maximum disjoint set (MDS) is a largest set of non-overlapping geometric shapes selected from a given set of candidate shapes…
- Low-rank approximation In mathematics, low-rank approximation refers to the process of approximating a given matrix by a matrix of lower rank. More precisely, it is a minimization…