On the complexity of the Double Digest Problem

Citation

Blazewicz J, Burke E, Jaroszewski M, Kasprzak M, Paliswiat B & Pryputniewicz P (2004) On the complexity of the Double Digest Problem. Control and Cybernetics, 33 (1), pp. 133-140.

Abstract
The problem of genome mapping is considered. It is showed that the Double Digest Problem (DDP) is NP-hard in its search version, while its decision version is trivially easy.

Keywords
computational complexity; DNA restriction maps

Journal
Control and Cybernetics: Volume 33, Issue 1