On the longest common rigid subsequence problem

DOI10.1007/s00453-008-9175-1zbMath1191.68216OpenAlexW2159782909MaRDI QIDQ848965

Moshe Lewenstein, Bin Ma, Nikhil Bansal, Zhang, Kaizhong

Publication date: 23 February 2010

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-008-9175-1

zbMATH Keywords

approximation algorithmslongest common subsequencemotif findinglongest common rigid subsequencepattern matching and computational biology

Mathematics Subject Classification ID

Searching and sorting (68P10) Pattern recognition, speech recognition (68T10)

Related Items (1)

Quick greedy computation for minimum common string partition

Uses Software

• TEIRESIAS

Cites Work

• Unnamed Item
• Unnamed Item
• Pattern recognition in several sequences: Consensus and alignment
• Optimization, approximation, and complexity classes
• Distinguishing string selection problems.
• Some APX-completeness results for cubic graphs
• Derandomized graph products
• Finding similar regions in many sequences
• Finding similar regions in many strings
• On the closest string and substring problems
• The Complexity of Some Problems on Subsequences and Supersequences
• On the Approximation of Shortest Common Supersequences and Longest Common Subsequences
• Combinatorial Pattern Matching

This page was built for publication: On the longest common rigid subsequence problem