Quick greedy computation for minimum common string partition

DOI10.1016/j.tcs.2014.05.006zbMath1360.68963MaRDI QIDQ2015138

Isaac Goldstein, Moshe Lewenstein

Publication date: 23 June 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2014.05.006

zbMATH Keywords

approximation algorithm; strings; pattern matching

Mathematics Subject Classification ID

68W25: Approximation algorithms

68W32: Algorithms on strings

Related Items

Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Minimum common string partition revisited
• On the longest common rigid subsequence problem
• The greedy algorithm for edit distance with moves
• Block edit models for approximate string matching
• On-line construction of suffix trees
• Edit distance with move operations
• Minimum common string partition problem: hardness and approximations
• Sorting Strings by Reversals and by Transpositions
• The greedy algorithm for the minimum common string partition problem
• Restricted Common Superstring and Restricted Common Supersequence
• Transforming cabbage into turnip
• A Space-Economical Suffix Tree Construction Algorithm
• Minimum Common String Partition Parameterized by Partition Size Is Fixed-Parameter Tractable
• Reversal Distance for Strings with Duplicates: Linear Time Approximation Using Hitting Set
• Mathematical Foundations of Computer Science 2005