Quick greedy computation for minimum common string partition

DOI10.1016/J.TCS.2014.05.006MaRDI QIDQ2015138zbMATH OpenOpenAlexFDO

Authors 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 algorithmpattern matchingstrings

Mathematics Subject Classification ID

Approximation algorithms (68W25) Algorithms on strings (68W32)

Recommendations

• Quick greedy computation for minimum common string partitions
• The greedy algorithm for the minimum common string partition problem
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Exponential and polynomial time algorithms for the minimum common string partition problem
• Minimum common string partition problem: hardness and approximations

Cites work

• scientific article; zbMATH DE number 1516705 (Why is no real title available?)
• scientific article; zbMATH DE number 2119725 (Why is no real title available?)
• A Space-Economical Suffix Tree Construction Algorithm
• Block edit models for approximate string matching
• Edit distance with move operations
• Mathematical Foundations of Computer Science 2005
• Minimum Common String Partition Parameterized by Partition Size Is Fixed-Parameter Tractable
• Minimum common string partition problem: hardness and approximations
• Minimum common string partition revisited
• On the longest common rigid subsequence problem
• On-line construction of suffix trees
• Restricted common superstring and restricted common supersequence
• Reversal Distance for Strings with Duplicates: Linear Time Approximation Using Hitting Set
• Sorting strings by reversals and by transpositions
• The greedy algorithm for edit distance with moves
• The greedy algorithm for the minimum common string partition problem
• Transforming cabbage into turnip

Cited in

(4)

• Minimum common string partition revisited
• Fast matching-based approximations for maximum duo-preservation string mapping and its weighted variant
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Quick greedy computation for minimum common string partitions

This page was built for publication: Quick greedy computation for minimum common string partition

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