Partial digest is hard to solve for erroneous input data
From MaRDI portal
Publication:817811
DOI10.1016/j.tcs.2005.08.030zbMath1086.68053OpenAlexW2021292788MaRDI QIDQ817811
Paolo Penna, Mark Cieliebak, Stephan J. Eidenbenz
Publication date: 20 March 2006
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2005.08.030
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Genetics and epigenetics (92D10)
Related Items
A fast algorithm for the partial digest problem ⋮ The minimum distance superset problem: formulations and algorithms ⋮ Coordinate Difference Matrices ⋮ On the complexity of constructing Golomb rulers
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Mapping DNA by stochastic relaxation
- On the equal-subset-sum problem
- A lower bound on the number of solutions to the probed partial digest problem
- A partial digest approach to restriction site mapping
- Lectures on proof verification and approximation algorithms
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- The restriction mapping problem revisited.
- The Structure of Homometric Sets