Can I read A Note on Models for Graph Representations on EtoBox?

A Note on Models for Graph Representations by Amos Korman; Shay Kutten is a Computer Science article available to read on EtoBox.

What is A Note on Models for Graph Representations about?

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 ar

Who reads A Note on Models for Graph Representations?

Author

Amos Korman; Shay Kutten

Publisher

Elsevier Science; Elsevier ; Elsevier BV (ISSN 0304-3975)

Published

2009

Language

EN

Field

Computer Science (Physical Sciences)