Some NP-Complete Geometric Problems

Garey, M. R., Graham, R. L., & Johnson, D. S. (1976). Some NP-Complete Geometric Problems. Proceedings of the Eighth Annual ACM Symposium on Theory of Computing.

Type

Conference paper

Intellectual base

Primary research

Year

1976

DOI

10.1145/800113.803626

Link

https://doi.org/10.1145/800113.803626

Cited by

1 citation across 1 artifact.

Domain-specific

• Square-Root Sum Problem
  • Repeated terms allow integer coefficients, although a formulation that supplies large coefficients directly in binary is a more succinct generalized input and must not automatically inherit every bound for the unit-coefficient problem.

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:70dd59e62364 · see in the full table