The greedy algorithm for the minimum common string partition problem

DOI10.1145/1103963.1103971MaRDI QIDQ2944502zbMATH OpenOpenAlexFDO

Authors Petr Kolman, Jiří Sgall, Marek Chrobak

Publication date 2 September 2015

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1103963.1103971

zbMATH Keywords

approximation algorithmsstring algorithms

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Approximation algorithms (68W25) Algorithms on strings (68W32)

Recommendations

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

Cited in

(15)

• Fixed-parameter tractability for the tree assembly problem
• Edit distance with block operations
• Parameterized tractability of the maximum-duo preservation string mapping problem
• Approximating reversal distance for strings with bounded number of duplicates
• Minimum common string partition: on solving large‐scale problem instances
• Permutation-constrained common string partitions with applications
• The complexity of finding common partitions of genomes with predefined block sizes
• Greedy Conjecture for Strings of Length 4
• A note on complexity of genetic mutations
• Quick greedy computation for minimum common string partition
• Solving the minimum common string partition problem with the help of ants
• Efficient algorithms for the block edit problems
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Permutation-constrained common string partitions with applications
• Quick greedy computation for minimum common string partitions

This page was built for publication: The greedy algorithm for the minimum common string partition problem

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