Minimum common string partition revisited

DOI10.1007/S10878-010-9370-2MaRDI QIDQ437061zbMATH OpenOpenAlexFDO

Authors Haitao Jiang, Binhai Zhu, Daming Zhu, Hong Zhu

Publication date 17 July 2012

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10878-010-9370-2

zbMATH Keywords

NP-completenessgenome rearrangementminimum common string partitionFPT algorithmsgenomic distance

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Recommendations

• Minimum common string partition revisited
• scientific article; zbMATH DE number 7740890
• Minimum common string partition problem: hardness and approximations
• Algorithms and Computation
• Minimum common string partition: on solving large‐scale problem instances
• Quick greedy computation for minimum common string partitions
• Quick greedy computation for minimum common string partition
• Exponential and polynomial time algorithms for the minimum common string partition problem

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2087046 (Why is no real title available?)
• scientific article; zbMATH DE number 2119725 (Why is no real title available?)
• Algorithms and Computation
• Approximating reversal distance for strings with bounded number of duplicates
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Mathematical Foundations of Computer Science 2005
• Parametrized complexity theory.
• 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

Cited in

(22)

• Fast matching-based approximations for maximum duo-preservation string mapping and its weighted variant
• Exponential and polynomial time algorithms for the minimum common string partition problem
• The complexity of finding common partitions of genomes with predefined block sizes
• scientific article; zbMATH DE number 5777888 (Why is no real title available?)
• The complexity of string partitioning
• Minimum common string partition revisited
• Revisiting the parameterized complexity of maximum-duo preservation string mapping
• Mathematical programming strategies for solving the minimum common string partition problem
• The Complexity of String Partitioning
• A (1.4 + epsilon)-Approximation Algorithm for the 2-Max-Duo Problem
• Minimum Common String Partition Parameterized by Partition Size Is Fixed-Parameter Tractable
• On the exact block cover problem
• Computational performance evaluation of two integer linear programming models for the minimum common string partition problem
• Minimum common string partition: on solving large‐scale problem instances
• Fixed-parameter tractability for minimum tree cut/paste distance and minimum common integer partition
• Algorithms and Computation
• Parameterized tractability of the maximum-duo preservation string mapping problem
• Minimum common string partition problem: hardness and approximations
• Quick greedy computation for minimum common string partition
• A \((1.4+\epsilon)\)-approximation algorithm for the 2-\textsc{Max-Duo} problem
• Permutation-constrained common string partitions with applications
• Permutation-constrained common string partitions with applications

This page was built for publication: Minimum common string partition revisited

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