Mathematical Foundations of Computer Science 2005

DOI10.1007/11549345MaRDI QIDQ5492891zbMATH OpenOpenAlexFDO

Authors Petr Kolman

Publication date 20 October 2006

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11549345

zbMATH Keywords

Approximation algorithmsString comparisonSorting by reversalsEdit distanceMinimum common string partition

Mathematics Subject Classification ID

Approximation algorithms (68W25)

Recommendations

• Approximating reversal distance for strings with bounded number of duplicates
• Reversal Distance for Strings with Duplicates: Linear Time Approximation Using Hitting Set
• Reversal distance for strings with duplicates: linear time approximation using hitting set
• Reversal distances for strings with few blocks or small alphabets
• (Prefix) reversal distance for (signed) strings with few blocks or small alphabets

Cited in

(16)

• Mathematical programming strategies for solving the minimum common string partition problem
• Adjacent Swaps on Strings
• Calculating distances for dissimilar strings: the shortest path formulation revisited
• On the Cost of Interchange Rearrangement in Strings
• Approximating reversal distance for strings with bounded number of duplicates
• Computational performance evaluation of two integer linear programming models for the minimum common string partition problem
• Minimum common string partition revisited
• Minimum common string partition: on solving large‐scale problem instances
• Reversal distance for strings with duplicates: linear time approximation using hitting set
• Reversal distances for strings with few blocks or small alphabets
• Quick greedy computation for minimum common string partition
• (Prefix) reversal distance for (signed) strings with few blocks or small alphabets
• Reversal Distance for Strings with Duplicates: Linear Time Approximation Using Hitting Set
• Reversals and Transpositions Over Finite Alphabets
• Quick greedy computation for minimum common string partitions
• Pattern matching with non overlapping reversals -- approximation and on-line algorithms

This page was built for publication: Mathematical Foundations of Computer Science 2005

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