首页    期刊浏览 2024年11月10日 星期日
登录注册

文章基本信息

  • 标题:Near Optimal Adjacency Labeling Schemes for Power-Law Graphs
  • 本地全文:下载
  • 作者:Casper Petersen ; Noy Rotbart ; Jakob Grue Simonsen
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2016
  • 卷号:55
  • 页码:133:1-133:15
  • DOI:10.4230/LIPIcs.ICALP.2016.133
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要:An adjacency labeling scheme labels the n nodes of a graph with bit strings in a way that allows, given the labels of two nodes, to determine adjacency based only on those bit strings. Though many graph families have been meticulously studied for this problem, a non-trivial labeling scheme for the important family of power-law graphs has yet to be obtained. This family is particularly useful for social and web networks as their underlying graphs are typically modelled as power-law graphs. Using simple strategies and a careful selection of a parameter, we show upper bounds for such labeling schemes of ~O(sqrt^{alpha}(n)) for power law graphs with coefficient alpha;, as well as nearly matching lower bounds. We also show two relaxations that allow for a label of logarithmic size, and extend the upper-bound technique to produce an improved distance labeling scheme for power-law graphs.
  • 关键词:Labeling schemes; Power-law graphs
国家哲学社会科学文献中心版权所有