On complexity of mutlidistance graph recognition in R^1

10/14/2017

∙

by   Mikhail Tikhomirov, et al.

∙

0

∙

share

Let A be a set of positive numbers. A graph G is called an A-embeddable graph in R^d if the vertices of G can be positioned in R^d so that the distance between endpoints of any edge is an element of A. We consider the computational problem of recognizing A-embeddable graphs in R^1 and classify all finite sets A by complexity of this problem in several natural variations.