Hexagonal unit network - a tool for proving the NP-completeness results of geometric problems (Q1071507)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Hexagonal unit network - a tool for proving the NP-completeness results of geometric problems |
scientific article |
Statements
Hexagonal unit network - a tool for proving the NP-completeness results of geometric problems (English)
0 references
1986
0 references
The special embedding of instances of the well-known NP-complete problem ''exact cover by 3-sets'' into hexagonal unit network is suggested for exhibiting polynomial transformation to geometric problems. In particular the NP-completeness of Euclidean clustering is proved and three interesting graph-theoretical corollaries are obtained.
0 references
exact cover by 3-sets
0 references
polynomial transformation
0 references
Euclidean clustering
0 references
