The Fine-Grained Complexity of Median and Center String Problems Under Edit Distance
From MaRDI portal
Publication:5874533
Cites work
- scientific article; zbMATH DE number 2090197 (Why is no real title available?)
- scientific article; zbMATH DE number 1446756 (Why is no real title available?)
- scientific article; zbMATH DE number 7561548 (Why is no real title available?)
- scientific article; zbMATH DE number 7650240 (Why is no real title available?)
- A new algorithm for optimal 2-constraint satisfaction and its implications
- An equivalence class for orthogonal vectors
- Approximation algorithms for multiple sequence alignment under a fixed evolutionary tree
- Clustered Integer 3SUM via Additive Combinatorics
- Conditional Lower Bounds for All-Pairs Max-Flow
- Consequences of Faster Alignment of Sequences
- Distinguishing string selection problems.
- Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
- Fine-grained I/O complexity via reductions: new lower bounds, faster algorithms, and a time hierarchy
- Fixed-parameter algorithms for CLOSEST STRING and related problems
- Hardness of RNA folding problem with four symbols
- Hardness results for the center and median string problems under the weighted and unweighted edit distances
- Higher lower bounds from the 3SUM conjecture
- Improved Approximation Algorithms for Tree Alignment
- Listing center strings under the edit distance metric
- Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
- Minimal Mutation Trees of Sequences
- More efficient algorithms for closest string and substring problems
- Multivariate fine-grained complexity of longest common subsequence
- On the closest string and substring problems
- SETH-based lower bounds for subset sum and bicriteria path
- Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made
- Subcubic equivalences between graph centrality problems, APSP and diameter
- Subtree isomorphism revisited
- The consensus string problem for a metric is NP-complete
- Tight conditional lower bounds for longest common increasing subsequence
- Topology of strings: median string is NP-complete
- Upper and lower bounds for dynamic data structures on strings
Cited in
(6)- Center and distinguisher for strings with unbounded alphabet
- On the Efficiency of the Hamming C-Centerstring Problems
- Topology of strings: median string is NP-complete
- Matching patterns with variables under edit distance
- Co-linear chaining with overlaps and gap costs
- The complexity of approximate pattern matching on de Bruijn graphs
This page was built for publication: The Fine-Grained Complexity of Median and Center String Problems Under Edit Distance
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5874533)
