Complexities of the centre and median string problems

DOI10.1007/3-540-44888-8_23MaRDI QIDQ3550844zbMATH OpenOpenAlexFDO

Authors François Nicolas, Eric Rivals

Publication date 6 April 2010

Published in Combinatorial Pattern Matching (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-44888-8_23

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Hardness results for the center and median string problems under the weighted and unweighted edit distances
• Topology of strings: median string is NP-complete
• On the Efficiency of the Hamming C-Centerstring Problems
• Median strings for k-nearest neighbour classification
• New approach to searching for string median and visualization of string clusters

Cited in

(14)

• Center and distinguisher for strings with unbounded alphabet
• A three-string approach to the closest string problem
• Listing center strings under the edit distance metric
• Optimal string clustering based on a Laplace-like mixture and EM algorithm on a set of strings
• scientific article; zbMATH DE number 1446756 (Why is no real title available?)
• scientific article; zbMATH DE number 2090197 (Why is no real title available?)
• On the Efficiency of the Hamming C-Centerstring Problems
• Efficient algorithms for consensus string problems minimizing both distance sum and radius
• Hardness results for the center and median string problems under the weighted and unweighted edit distances
• Topology of strings: median string is NP-complete
• New approach to searching for string median and visualization of string clusters
• The k-centre problem for classes of cyclic words
• Randomized fixed-parameter algorithms for the closest string problem
• Median strings for k-nearest neighbour classification

This page was built for publication: Complexities of the centre and median string problems

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