Partial digest is hard to solve for erroneous input data
From MaRDI portal
Publication:817811
DOI10.1016/j.tcs.2005.08.030zbMath1086.68053MaRDI 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
68Q25: Analysis of algorithms and problem complexity
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
92D10: Genetics and epigenetics
Related Items
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