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
Daniel Gibney, Gary Hoppenworth, Jason Bentley, 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
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- 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
- Improved Approximation Algorithms for Tree Alignment
- Subcubic Equivalences Between Graph Centrality Problems, APSP and Diameter
- Consequences of Faster Alignment of Sequences
- The consensus string problem for a metric is NP-complete
- Subtree Isomorphism Revisited
- 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
- Conditional Lower Bounds for All-Pairs Max-Flow
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)
