Charge and reduce: A fixed-parameter algorithm for string-to-string correction

DOI10.1016/j.disopt.2010.10.003zbMath1248.90065OpenAlexW2077167828MaRDI QIDQ456695

Henning Fernau, Serena Lee-Cultura, Faisal N. Abu-Khzam, Ulrike Stege, Michael A. Langston

Publication date: 16 October 2012

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2010.10.003

zbMATH Keywords

fixed-parameter algorithmcharge and reducestring-to-string correction

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items (4)

On the parameterised complexity of string morphism problems ⋮ Adaptive Computation of the Swap-Insert Correction Distance ⋮ Maximum common induced subgraph parameterized by vertex cover ⋮ Using swaps and deletes to make strings match

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An Efficient Exact Algorithm for Constraint Bipartite Vertex Cover
• Searching Trees: An Essay
• An Extension of the String-to-String Correction Problem
• The Complexity of Some Problems on Subsequences and Supersequences
• Error Detecting and Error Correcting Codes

This page was built for publication: Charge and reduce: A fixed-parameter algorithm for string-to-string correction