Displaying similar documents to “An Observation about Variations of the Diffie-Hellman Assumption”

Combinatorial optimization in DNA mapping — A computational thread of the simplified partial digest problem

Jacek Blazewicz, Marta Kasprzak (2005)

RAIRO - Operations Research - Recherche Opérationnelle

Similarity:

In the paper, the problem of the genome mapping of DNA molecules, is presented. In particular, the new approach — the Simplified Partial Digest Problem (SPDP), is analyzed. This approach, although easy in laboratory implementation and robust with respect to measurement errors, when formulated in terms of a combinatorial search problem, is proved to be strongly NP-hard for the general error-free case. For a subproblem of the SPDP, a simple O( n log n )-time algorithm is given, where n is a number...

An introduction to multiprocessor scheduling.

J.K. Lenstra, A.H.G. Rinnooy (1981)

Qüestiió

Similarity:

This is a tutorial survey of recent results in the area of multiprocessor scheduling. Computational complexity theory provides the framework in which these results are presented. They involve on one hand the development of new polynomial optimization algorithms, and on the other hand the application of the concept of NP-hardness as well as the analysis of approximation algorithms.