Listing Center Strings Under the Edit Distance Metric

DOI10.1007/978-3-319-26626-8_57zbMath1473.68221OpenAlexW2405796391MaRDI QIDQ5743548

Taisuke Izumi, Hiromitsu Maji

Publication date: 5 February 2016

Published in: Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-26626-8_57

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Algorithms on strings (68W32)

Related Items (1)

The Fine-Grained Complexity of Median and Center String Problems Under Edit Distance

Cites Work

• On the parameterized complexity of the repetition free longest common subsequence problem
• On covering problems of codes
• Fixed-parameter algorithms for CLOSEST STRING and related problems
• Distinguishing string selection problems.
• On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
• Topology of strings: median string is NP-complete
• Hardness results for the center and median string problems under the weighted and unweighted edit distances
• Hardness of Longest Common Subsequence for Sequences with Bounded Run-Lengths
• On the Closest String via Rank Distance
• On the closest string and substring problems
• Closest Substring Problems with Small Distances
• More Efficient Algorithms for Closest String and Substring Problems
• The Complexity of Some Problems on Subsequences and Supersequences
• On the Approximation of Shortest Common Supersequences and Longest Common Subsequences
• Efficient Algorithms for the Closest String and Distinguishing String Selection Problems

This page was built for publication: Listing Center Strings Under the Edit Distance Metric