On the approximation of shortest common supersequences and longest common subsequences

DOI10.1007/3-540-58201-0_68MaRDI QIDQ4632426zbMATH OpenOpenAlexFDO

Authors Tao Jiang, Ming Li

Publication date 29 April 2019

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-58201-0_68

zbMATH Keywords

longest common subsequenceperformance ratiovertex coverKolmogorov complexityinput sequence

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Algorithms on strings (68W32)

Recommendations

• On the Approximation of Shortest Common Supersequences and Longest Common Subsequences
• Approximation algorithms for the shortest common superstring problem
• scientific article; zbMATH DE number 827942
• scientific article; zbMATH DE number 1859299
• Maximal common subsequences and minimal common supersequences

Cites work

• scientific article; zbMATH DE number 4174365 (Why is no real title available?)
• scientific article; zbMATH DE number 3767009 (Why is no real title available?)
• scientific article; zbMATH DE number 107774 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1256636 (Why is no real title available?)
• A Sentence-to-Sentence Clustering Procedure for Pattern Analysis
• Algorithms for the Longest Common Subsequence Problem
• An Efron-Stein inequality for nonsymmetric statistics
• Computing a longest common subsequence for a set of strings
• Linear approximation of shortest superstrings
• Longest common subsequences of two random sequences
• On approximating the longest path in a graph
• On the hardness of approximating minimization problems
• Optimization, approximation, and complexity classes
• Statistical properties of finite sequences with high Kolmogorov complexity
• The Complexity of Some Problems on Subsequences and Supersequences
• The String-to-String Correction Problem
• The shortest common supersequence problem over binary alphabet is NP- complete
• Theory and algorithms for plan merging

Cited in

(10)

• Improved heuristics and a genetic algorithm for finding short supersequences
• scientific article; zbMATH DE number 4095235 (Why is no real title available?)
• scientific article; zbMATH DE number 1859299 (Why is no real title available?)
• scientific article; zbMATH DE number 827942 (Why is no real title available?)
• The constrained shortest common supersequence problem
• Combined super-/substring and super-/subsequence problems
• Approximating minimum keys and optimal substructure screens
• Improved non-approximability results for minimum vertex cover with density constraints
• Constrained TSP and low-power computing
• On the Approximation of Shortest Common Supersequences and Longest Common Subsequences

This page was built for publication: On the approximation of shortest common supersequences and longest common subsequences

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