Labeling Schemes with Queries

Details Labeling Schemes with Queries Labeling Schemes with Queries

2006-09-29

arxiv.org/abs/cs/0609163v1

Computer Science

Distributed, Parallel, and Cluster Computing

Scientific paper

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 $\cF$ labels the vertices of all graphs in $\cF$ such that for every graph $G\in\cF$ and every two vertices $u,v\in 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 {\em query}) enables us to reduce the label size of many labeling schemes significantly.

Affiliated with

Also associated with

No associations

Rating

Labeling Schemes with Queries does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Labeling Schemes with Queries, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Labeling Schemes with Queries will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-184261