Labeling Schemes with Queries

الأصل · EN

We study the question of ``how robust are the known lower bounds of labeling schemes when one increases the number of consulted labels''. Let f be a function on pairs of vertices. An f-labeling scheme for a family of graphs labels the vertices of all graphs in such that for every graph G∈ and every two vertices u,v∈ G, the value f(u,v) can be inferred by merely inspecting the labels of u and v. This paper introduces a natural generalization: the notion of f-labeling schemes with queries, in which the value f(u,v) can be inferred by inspecting not only the labels of u and v but possibly the labels of some additional vertices. We show that inspecting the label of a single additional vertex (one query) enables us to reduce the label size of many labeling schemes significantly.