Labeling Schemes with Queries
| dc.creator | Korman, Amos | |
| dc.creator | Kutten, Shay | |
| dc.date | 2006-09-29 | |
| dc.date.accessioned | 2026-07-07T07:23:59Z | |
| dc.date.available | 2026-07-07T07:23:59Z | |
| dc.description | 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. | |
| dc.identifier | https://arxiv.org/abs/cs/0609163 | |
| dc.identifier | http://arxiv.org/abs/cs/0609163 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/116184 | |
| dc.subject | Distributed, Parallel, and Cluster Computing | |
| dc.title | Labeling Schemes with Queries | |
| dc.type | text |