%0 Journal Article
%T Near-optimal adjacency labeling scheme for power-law graphs
%A Casper Petersen
%A Noy Rotbart
%A Jakob Grue Simonsen
%A Christian Wulff-Nilsen
%J Computer Science
%D 2015
%I arXiv
%X An adjacency labeling scheme is a method that assigns labels to the vertices of a graph such that adjacency between vertices can be inferred directly from the assigned label, without using a centralized data structure. We devise adjacency labeling schemes for the family of power-law graphs. This family that has been used to model many types of networks, e.g. the Internet AS-level graph. Furthermore, we prove an almost matching lower bound for this family. We also provide an asymptotically near- optimal labeling scheme for sparse graphs. Finally, we validate the efficiency of our labeling scheme by an experimental evaluation using both synthetic data and real-world networks of up to hundreds of thousands of vertices.
%U http://arxiv.org/abs/1502.03971v1