Topology of strings: median string is NP-complete

DOI10.1016/S0304-3975(97)00240-5zbMATH Open0940.68116MaRDI QIDQ1978500FDOQ1978500

Authors: Colin de la Higuera, Francisco Casacuberta 

Publication date: 4 June 2000

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

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

zbMATH Keywords

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

Mathematics Subject Classification ID

Pattern recognition, speech recognition (68T10)

Cites Work

• Title not available (Why is that?)
• The String-to-String Correction Problem
• Title not available (Why is that?)
• Title not available (Why is that?)
• From the median to the generalized center
• Finding approximate patterns in strings
• A survey of multiple sequence comparison methods
• Approximation algorithms for tree alignment with a given phylogeny
• Multiple sequence comparison -- a peptide matching approach

Cited In (17)

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

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)