作者: Thomas Bläsius , Tobias Friedrich , Anton Krohmer
DOI: 10.4230/LIPICS.ESA.2016.15
关键词:
摘要: Hyperbolic random graphs share many common properties with complex real-world networks; e.g., small diameter and average distance, large clustering coefficient, a power-law degree sequence adjustable exponent beta. Thus, when analyzing algorithms for networks, potentially more realistic results can be achieved by assuming the input to hyperbolic graph of size n. The worst-case run-time is then replaced expected or bounds that hold high probability (whp), i.e., 1-O(1/n). Though structural have been studied, almost no algorithmic are known. Divide-and-conquer an important design principle works particularly well if instance admits separators. We show in fact comparatively More precisely, we they balanced separator hierarchies separators O(n^{3/2-beta/2}), O(log n), O(1) 2 < beta 3, = 3 beta, respectively. infer these whp treewidth O(log^2 For \beta this matches known lower bound. To demonstrate usefulness our results, give several applications.