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

An NP-complete matching problem

โœ Scribed by David A. Plaisted; Samuel Zaks

Publisher
Elsevier Science
Year
1980
Tongue
English
Weight
847 KB
Volume
2
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

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

The STO problem is NP-complete
The STO problem is NP-complete
โœ P. Krysta; L. Pacholski ๐Ÿ“‚ Article ๐Ÿ“… 1999 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 233 KB

We prove that the problem STO of deciding whether or not a finite set E of term equations is subject to occur-check is in NP. E is subject to occur-check if the execution of the Martelli-Montanari unification algorithm gives for input E a set E โˆช {x = t}, where t = x and x appears in t. Apt et al. (

A simplified NP-complete MAXSAT problem
A simplified NP-complete MAXSAT problem
โœ Venkatesh Raman; B. Ravikumar; S.Srinivasa Rao ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 639 KB

It is shown that the MAXZSAT problem is NP-complete even if every variable appears in at most three clauses. However, if every variable appears in at most two clauses, it is shown that it (and even the general MAXSAT problem) can be solved in linear time. When every variable appears in at most three