Fast matching-based approximations for maximum duo-preservation string mapping and its weighted variant

DOI10.4230/LIPICS.CPM.2018.5MaRDI QIDQ5140766zbMATH OpenFDO

Authors Brian Brubach

Publication date 16 December 2020

Full work available at URL https://doi.org/10.4230/LIPICS.CPM.2018.5

zbMATH Keywords

approximation algorithmmaximum duo-preservation string mappingminimum common string partitionstreaming algorithmstring comparison

Mathematics Subject Classification ID

Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27) Algorithms on strings (68W32)

Recommendations

• Further improvement in approximating the maximum duo-preservation string mapping problem
• Improved approximation for the maximum duo-preservation string mapping problem
• A 7/2-approximation algorithm for the maximum duo-preservation string mapping problem
• The Maximum Duo-Preservation String Mapping Problem with Bounded Alphabet *
• A family of approximation algorithms for the maximum duo-preservation string mapping problem

Cites work

• A 7/2-approximation algorithm for the maximum duo-preservation string mapping problem
• A family of approximation algorithms for the maximum duo-preservation string mapping problem
• Algorithms and Computation
• Approximating reversal distance for strings with bounded number of duplicates
• Approximating the true evolutionary distance between two genomes
• Approximating weighted duo-preservation in comparative genomics
• Approximation algorithms for bipartite matching with metric and geometric costs
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Fibonacci heaps and their uses in improved network optimization algorithms
• Further improvement in approximating the maximum duo-preservation string mapping problem
• scientific article; zbMATH DE number 3889282 (Why is no real title available?)
• Improved approximation for the maximum duo-preservation string mapping problem
• Linear-time approximation for maximum weight matching
• Mathematical programming strategies for solving the minimum common string partition problem
• Max flows in O(nm) time, or better
• Minimum Common String Partition Parameterized by Partition Size Is Fixed-Parameter Tractable
• Minimum common string partition revisited
• Quick greedy computation for minimum common string partition
• Reversal Distance for Strings with Duplicates: Linear Time Approximation Using Hitting Set
• Revisiting the parameterized complexity of maximum-duo preservation string mapping
• Solving the maximum duo-preservation string mapping problem with linear programming
• The greedy algorithm for edit distance with moves
• The string edit distance matching problem with moves

Cited in

(3)

• Further improvement in approximating the maximum duo-preservation string mapping problem
• Approximating weighted duo-preservation in comparative genomics
• The Maximum Duo-Preservation String Mapping Problem with Bounded Alphabet *

This page was built for publication: Fast matching-based approximations for maximum duo-preservation string mapping and its weighted variant

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