Strong" NP-Completeness Results

M. R Garey, D. S. J. (1978). Strong" NP-Completeness Results: Motivation, Examples, and Implications. ACM.

Type

Book chapter

Intellectual base

Review or monograph

Year

1978

DOI

10.1145/322077.322090

Link

https://doi.org/10.1145/322077.322090

Cited by

1 citation across 1 artifact.

Domain-specific

• Independent set (graph theory)
  • Independent, maximal and maximum are distinct, weighted variants change the objective and the set is a clique only in the complement graph.

Verification

This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.

Registry ID ref:07e5f0a868b4 · see in the full table