arXiv
Open Access
2014
On computational complexity of length embeddability of graphs
Mikhail Tikhomirov
Abstrak
A graph $G$ is embeddable in $\mathbb{R}^d$ if vertices of $G$ can be assigned with points of $\mathbb{R}^d$ in such a way that all pairs of adjacent vertices are at the distance 1. We show that verifying embeddability of a given graph in $\mathbb{R}^d$ is NP-hard in the case $d > 2$ for all reasonable notions of embeddability.
Penulis (1)
M
Mikhail Tikhomirov
Akses Cepat
Informasi Jurnal
- Tahun Terbit
- 2014
- Bahasa
- en
- Sumber Database
- arXiv
- Akses
- Open Access ✓