Topology of strings: median string is NP-complete

DOI10.1016/S0304-3975(97)00240-5zbMath0940.68116MaRDI QIDQ1978500

Francisco Casacuberta, Colin de la Higuera

Publication date: 4 June 2000

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

NP-complete problemsmultiple sequence alignmentstring-to-string correctionLevenshtein distancegeneralised median

Mathematics Subject Classification ID

Pattern recognition, speech recognition (68T10)

Related Items (9)

Heuristics for the generalized median graph problem ⋮ Computing the Expected Edit Distance from a String to a Probabilistic Finite-State Automaton ⋮ The Fine-Grained Complexity of Median and Center String Problems Under Edit Distance ⋮ Generalized median graph computation by means of graph embedding in vector spaces ⋮ Listing Center Strings Under the Edit Distance Metric ⋮ An efficient approach for the rank aggregation problem ⋮ Computing the Expected Edit Distance from a String to a PFA ⋮ Optimal string clustering based on a Laplace-like mixture and EM algorithm on a set of strings ⋮ Hardness results for the center and median string problems under the weighted and unweighted edit distances

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A survey of multiple sequence comparison methods
• Multiple sequence comparison -- a peptide matching approach
• Approximation algorithms for tree alignment with a given phylogeny
• Finding approximate patterns in strings
• From the median to the generalized center
• The String-to-String Correction Problem

This page was built for publication: Topology of strings: median string is NP-complete