Complexities of the centre and median string problems

DOI10.1007/3-540-44888-8_23zbMATH Open1279.68107OpenAlexW1589348829MaRDI QIDQ3550844FDOQ3550844

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)

• Optimal string clustering based on a Laplace-like mixture and EM algorithm on a set of strings
• Randomized fixed-parameter algorithms for the closest string problem
• Title not available (Why is no real title available?)
• A three-string approach to the closest string problem
• Hardness results for the center and median string problems under the weighted and unweighted edit distances
• Title not available (Why is no real title available?)
• Efficient algorithms for consensus string problems minimizing both distance sum and radius
• The k-centre problem for classes of cyclic words
• Center and distinguisher for strings with unbounded alphabet
• On the Efficiency of the Hamming C-Centerstring Problems
• New approach to searching for string median and visualization of string clusters
• Listing center strings under the edit distance metric
• Topology of strings: median string is NP-complete
• 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)