Affordable Access

Publisher Website

A note on models for graph representations

Theoretical Computer Science
Publication Date
DOI: 10.1016/j.tcs.2008.10.036
  • Distributed Algorithms
  • Informative Labeling Schemes
  • Compact Routing Schemes
  • Dynamic Networks


Abstract This paper is intended more to ask questions than give answers. Specifically, we consider models for labeling schemes, and discuss issues regarding the number of labels consulted vs. the sizes of the labels. Recently, quite a few papers studied methods for representing network properties by assigning informative labels to the vertices of a network. Consider a graph function f on pairs of vertices (for example, f can be the distance function). In an f - labeling scheme, the labels are constructed in such a way so that given the labels of any two vertices u and v , one can compute the function f ( u , v ) (e.g. the graph distance between u and v ) just by looking at these two labels. Some very involved lower bounds for the sizes of the labels were proven. Also, some highly sophisticated labeling schemes were developed to ensure short labels. In this paper, we demonstrate that such lower bounds are very sensitive to the number of vertices consulted. That is, we show several constructions of such labeling schemes that beat the lower bounds by large margins. Moreover, as opposed to the strong technical skills that were needed to develop the traditional labeling schemes, most of our schemes are almost trivial. The catch is that in our model, one needs to consult the labels of three vertices instead of two. That is, a query about vertices u and v can access also the label of some third vertex w ( w is determined by the labels of u and v ). More generally, we address the model in which a query about vertices u and v can access also the labels of c other vertices. We term our generalized model labeling schemes with queries. The main importance of this model is theoretical. Specifically, this paper may serve as a first step towards investigating different tradeoffs between the amount of labels consulted and the amount of information stored at each vertex. As we show, if all vertices can be consulted then the problem almost reduces to the corresponding sequential problem. On the other hand, consulting just the labels of u and v (or even just the label of u ) reduces the problem to a purely distributed one. Therefore, in a sense, our model spans a range of intermediate notions between the sequential and the distributed settings. In addition to the theoretical interest, we also show cases that schemes constructed for our model can be translated to the traditional model or to the sequential model, thus, simplifying the construction for those models as well. For implementing query labeling schemes in a distributed environment directly, we point at a potential usage for some new paradigms that became common recently, such as P2P and overlay networks.

There are no comments yet on this publication. Be the first to share your thoughts.