๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Complete problems for monotone NP

โœ Scribed by Iain A. Stewart

Publisher
Elsevier Science
Year
1995
Tongue
English
Weight
768 KB
Volume
145
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

Neural networks for NP-complete problems
Neural networks for NP-complete problems
โœ Marco Budinich ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 547 KB

combinatorial optimization is an active field of research in Neural Networks. Since the first attempts to solve the travelling salesman problem with Hopfield nets several progresses have been made. I will present some Neural Network approximate solutions for NP-complete problems that have a sound ma

NP-complete scheduling problems
NP-complete scheduling problems
โœ J.D. Ullman ๐Ÿ“‚ Article ๐Ÿ“… 1975 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 423 KB

We show that the problem of finding an optimal schedule for a set of jobs is NPcomplete even in the following two restricted cases. (1) All jobs require one time unit. (2) All jobs require one or two time units, and there are only two processor resolving (in the negative a conjecture of R. L. Grah

DNA Models and Algorithms for NP-Complet
DNA Models and Algorithms for NP-Complete Problems
โœ Eric Bach; Anne Condon; Elton Glaser; Celena Tanguay ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 488 KB

A goal of research on DNA computing is to solve problems that are beyond the capabilities of the fastest silicon-based supercomputers. Adleman and Lipton present exhaustive search algorithms for 3Sat and 3-coloring, which can only be run on small instances and, hence, are not practical. In this pape