Partial digest is hard to solve for erroneous input data

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

zbMATH Keywords

partial digestphysical DNA mappingpoint reconstructionturnpike problem

Mathematics Subject Classification ID

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 (4)

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

This page was built for publication: Partial digest is hard to solve for erroneous input data