论文标题
$δ$ hyperbolic图的偏心地形
Eccentricity terrain of $δ$-hyperbolic graphs
论文作者
论文摘要
A graph $G=(V,E)$ is $δ$-hyperbolic if for any four vertices $u,v,w,x$, the two larger of the three distance sums $d(u,v)+d(w,x)$, $d(u,w)+d(v,x)$, and $d(u,x)+d(v,w)$ differ by at most $2δ\geq 0$.最近的工作表明，许多现实世界图具有少量的$δ$。本文介绍了$δ$ - 遗传图的怪异地形。偏心函数$ e_g（v）= \ max \ {d（v，u）：u \ in v \} $ partitions $ g $的顶点集合到怪异层中的顶点集$ c_ {k {k}（g）= \ {v \ in v：e（e（e（e（e（e（e）， $ rad（g）= \ min \ {e_g（v）：v \ in v \} $是$ g $的半径。论文研究了沿最短路径的顶点的偏心层，并识别了诸如山丘，平原，山谷，露台和高原等地形特征。它介绍了$β$ -Pseudoconvexity的概念，这意味着Gromov的$ε$ - Quasiconvexity，并说明了$Δ$Δ$ - 喂养bolicbolic图的丰度。特别是，它表明所有集合$ c _ {\ leq k}（g）= \ {v \ in v：e_g（v）\ leq rad（g） + k \} $，$ k \ in \ mathbb {n} $ in \ mathbb {n} $，是$（2δ-1）$ - pseudoconvex。另外，获得了顶点的偏心率的几个边界，这些边界产生了一些有效近似所有偏心率的方法。呈现$ O（δ| E |）$ time怪异近似$ \ hat {e}（v）$，对于所有v $中的所有$ v \，都使用了两个相互距离的顶点距离并满足$ e_g（v）-2Δ\ leq leq leq \ hat {e}（e}（e}（e}（v）\ leq leq leq e__g} $）$。它还显示了两个偏心率的存在，近似跨越树$ t $，一种在$ o（δ| e |）$ time中构造，另一个在$ o（| e |）$时间中，满足$ {e} _g（v）\ leq e_t（v）\ leq e_t（v） e_t（v）\ leq {e} _g（v）+6δ$。因此，一棵树的偏心地形给出了$Δ$ - 氢肉片图的偏心域的良好近似值（最新误差$ o（δ））$。
A graph $G=(V,E)$ is $δ$-hyperbolic if for any four vertices $u,v,w,x$, the two larger of the three distance sums $d(u,v)+d(w,x)$, $d(u,w)+d(v,x)$, and $d(u,x)+d(v,w)$ differ by at most $2δ\geq 0$. Recent work shows that many real-world graphs have small hyperbolicity $δ$. This paper describes the eccentricity terrain of a $δ$-hyperbolic graph. The eccentricity function $e_G(v)=\max\{d(v,u) : u \in V\}$ partitions the vertex set of $G$ into eccentricity layers $C_{k}(G) = \{v \in V : e(v)=rad(G)+k\}$, $k \in \mathbb{N}$, where $rad(G)=\min\{e_G(v): v\in V\}$ is the radius of $G$. The paper studies the eccentricity layers of vertices along shortest paths, identifying such terrain features as hills, plains, valleys, terraces, and plateaus. It introduces the notion of $β$-pseudoconvexity, which implies Gromov's $ε$-quasiconvexity, and illustrates the abundance of pseudoconvex sets in $δ$-hyperbolic graphs. In particular, it shows that all sets $C_{\leq k}(G)=\{v\in V : e_G(v) \leq rad(G) + k\}$, $k\in \mathbb{N}$, are $(2δ-1)$-pseudoconvex. Additionally, several bounds on the eccentricity of a vertex are obtained which yield a few approaches to efficiently approximating all eccentricities. An $O(δ|E|)$ time eccentricity approximation $\hat{e}(v)$, for all $v\in V$, is presented that uses distances to two mutually distant vertices and satisfies $e_G(v)-2δ\leq \hat{e}(v) \leq {e_G}(v)$. It also shows existence of two eccentricity approximating spanning trees $T$, one constructible in $O(δ|E|)$ time and the other in $O(|E|)$ time, which satisfy ${e}_G(v) \leq e_T(v) \leq {e}_G(v)+4δ+1$ and ${e}_G(v) \leq e_T(v) \leq {e}_G(v)+6δ$, respectively. Thus, the eccentricity terrain of a tree gives a good approximation (up-to an additive error $O(δ))$ of the eccentricity terrain of a $δ$-hyperbolic graph.
