Topology of strings: median string is NP-complete

DOI10.1016/S0304-3975(97)00240-5MaRDI QIDQ1978500zbMATH OpenFDO

Authors Colin de la Higuera, Francisco Casacuberta

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)

Recommendations

• Complexities of the centre and median string problems
• The Fine-Grained Complexity of Median and Center String Problems Under Edit Distance
• Recognizing string graphs in NP
• The consensus string problem for a metric is NP-complete
• Some computations in string topology
• scientific article; zbMATH DE number 1336330
• String graphs. II: Recognizing string graphs is NP-hard
• The transposition median problem is NP-complete

Cites work

• scientific article; zbMATH DE number 3825216 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 828444 (Why is no real title available?)
• A survey of multiple sequence comparison methods
• Approximation algorithms for tree alignment with a given phylogeny
• Finding approximate patterns in strings
• From the median to the generalized center
• Multiple sequence comparison -- a peptide matching approach
• The String-to-String Correction Problem

Cited in

(17)

• Listing center strings under the edit distance metric
• The computational complexity of calculating partition functions of optimal medians with Hamming distance
• NP-completeness of special string editing problems
• The consensus string problem for a metric is NP-complete
• Optimal string clustering based on a Laplace-like mixture and EM algorithm on a set of strings
• Generalized median graph computation by means of graph embedding in vector spaces
• scientific article; zbMATH DE number 1446756 (Why is no real title available?)
• scientific article; zbMATH DE number 2090197 (Why is no real title available?)
• Computing the expected edit distance from a string to a probabilistic finite-state automaton
• Computing the expected edit distance from a string to a PFA
• The Fine-Grained Complexity of Median and Center String Problems Under Edit Distance
• Hardness results for the center and median string problems under the weighted and unweighted edit distances
• Heuristics for the generalized median graph problem
• New approach to searching for string median and visualization of string clusters
• Complexities of the centre and median string problems
• scientific article; zbMATH DE number 4057049 (Why is no real title available?)
• An efficient approach for the rank aggregation problem

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

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