文章基本信息

标题：Hyperbolic Random Graphs: Separators and Treewidth
本地全文：下载
作者：Thomas Bl{\"a}sius ; Tobias Friedrich ; Anton Krohmer 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：57
页码：15:1-15:16
DOI：10.4230/LIPIcs.ESA.2016.15
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Hyperbolic random graphs share many common properties with complex real-world networks; e.g., small diameter and average distance, large clustering coefficient, and a power-law degree sequence with adjustable exponent beta. Thus, when analyzing algorithms for large networks, potentially more realistic results can be achieved by assuming the input to be a hyperbolic random graph of size n. The worst-case run-time is then replaced by the expected run-time or by bounds that hold with high probability (whp), i.e., with probability 1-O(1/n). Though many structural properties of hyperbolic random graphs have been studied, almost no algorithmic results are known. Divide-and-conquer is an important algorithmic design principle that works particularly well if the instance admits small separators. We show that hyperbolic random graphs in fact have comparatively small separators. More precisely, we show that they can be expected to have balanced separator hierarchies with separators of size O(n^{3/2-beta/2}), O(log n), and O(1) if 2 < beta < 3, beta = 3, and 3 < beta, respectively. We infer that these graphs have whp a treewidth of O(n^{3/2-beta/2}), O(log^2 n), and O(log n), respectively. For 2 < \beta < 3, this matches a known lower bound. To demonstrate the usefulness of our results, we give several algorithmic applications.
关键词：hyperbolic random graphs; scale-free networks; power-law graphs; separators; treewidth