On the approximation of shortest common supersequences and longest common subsequences

DOI10.1007/3-540-58201-0_68zbMath1422.68119OpenAlexW1903636486MaRDI QIDQ4632426

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

Kolmogorov complexityvertex coverperformance ratiolongest common subsequenceinput sequence

Mathematics Subject Classification ID

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

Related Items (3)

Constrained TSP and low-power computing ⋮ Approximating minimum keys and optimal substructure screens ⋮ Improved non-approximability results for minimum vertex cover with density constraints

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On approximating the longest path in a graph
• Computing a longest common subsequence for a set of strings
• An Efron-Stein inequality for nonsymmetric statistics
• The shortest common supersequence problem over binary alphabet is NP- complete
• Optimization, approximation, and complexity classes
• Theory and algorithms for plan merging
• Longest common subsequences of two random sequences
• The Complexity of Some Problems on Subsequences and Supersequences
• A Sentence-to-Sentence Clustering Procedure for Pattern Analysis
• Algorithms for the Longest Common Subsequence Problem
• Statistical properties of finite sequences with high Kolmogorov complexity
• Linear approximation of shortest superstrings
• The String-to-String Correction Problem
• On the hardness of approximating minimization problems

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