On computational complexity of length embeddability of graphs

DOI10.1016/j.disc.2016.05.011zbMath1339.05264arXiv1410.5555OpenAlexW1860256426MaRDI QIDQ2629266

Mikhail Tikhomirov

Publication date: 5 July 2016

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1410.5555

zbMATH Keywords

computational complexitydistance graphgraph embedding

Mathematics Subject Classification ID

Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

Turán-type results for distance graphs in an infinitesimal plane layer, On complexity of multidistance graph recognition in \(\mathbb{R}^1\), Minimal graphs with respect to geometric distance realizability

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the chromatic numbers of spheres in \(\mathbb R^n\)
• On the chromatic numbers of spheres in Euclidean spaces
• Borsuk's problem and the chromatic numbers of some metric spaces
• Coloring Distance Graphs and Graphs of Diameters
• On the Computational Complexity of Degenerate Unit Distance Representations of Graphs
• Research Problems in Discrete Geometry
• On Sets of Distances of n Points