The Fine-Grained Complexity of Median and Center String Problems Under Edit Distance
From MaRDI portal
Publication:5874533
DOI10.4230/LIPICS.ESA.2020.61OpenAlexW3081524518MaRDI QIDQ5874533FDOQ5874533
Authors: Gary Hoppenworth, Jason Bentley, Daniel Gibney, Sharma V. Thankachan 
Publication date: 7 February 2023
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2020/12927/pdf/LIPIcs-ESA-2020-61.pdf/
Cites Work
- Fixed-parameter algorithms for CLOSEST STRING and related problems
- Distinguishing string selection problems.
- On the closest string and substring problems
- More efficient algorithms for closest string and substring problems
- 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
- Topology of strings: median string is NP-complete
- Minimal Mutation Trees of Sequences
- Fine-grained I/O complexity via reductions: new lower bounds, faster algorithms, and a time hierarchy
- Improved Approximation Algorithms for Tree Alignment
- Subcubic equivalences between graph centrality problems, APSP and diameter
- Consequences of Faster Alignment of Sequences
- Title not available (Why is that?)
- Title not available (Why is that?)
- The consensus string problem for a metric is NP-complete
- Subtree isomorphism revisited
- Multivariate fine-grained complexity of longest common subsequence
- Tight conditional lower bounds for longest common increasing subsequence
- Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made
- Hardness of RNA folding problem with four symbols
- Higher lower bounds from the 3SUM conjecture
- Listing center strings under the edit distance metric
- SETH-based lower bounds for subset sum and bicriteria path
- Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
- Upper and lower bounds for dynamic data structures on strings
- Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
- Hardness results for the center and median string problems under the weighted and unweighted edit distances
- Title not available (Why is that?)
- Conditional Lower Bounds for All-Pairs Max-Flow
- Title not available (Why is that?)
Cited In (6)
- Center and distinguisher for strings with unbounded alphabet
- On the Efficiency of the Hamming C-Centerstring Problems
- Co-linear chaining with overlaps and gap costs
- The complexity of approximate pattern matching on de Bruijn graphs
- Topology of strings: median string is NP-complete
- Matching patterns with variables under edit distance
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)
