[HTML][HTML] Eccentricity terrain of δ-hyperbolic graphs
FF Dragan, HM Guarnera - Journal of Computer and System Sciences, 2020 - Elsevier
Journal of Computer and System Sciences, 2020•Elsevier
Abstract 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), d (u, x)+ d (v, w) differ by at most 2
δ≥ 0. This paper describes the eccentricity terrain of a δ-hyperbolic graph. The eccentricity
function e G (v)= max{d (v, u): u∈ V} partitions vertices of G into eccentricity layers C k
(G)={v∈ V: e G (v)= rad (G)+ k}, k∈ N, where rad (G)= min{e G (v): v∈ V} is the radius of G.
The paper studies the eccentricity layers of vertices along shortest paths, identifying such …
the three distance sums d (u, v)+ d (w, x), d (u, w)+ d (v, x), d (u, x)+ d (v, w) differ by at most 2
δ≥ 0. This paper describes the eccentricity terrain of a δ-hyperbolic graph. The eccentricity
function e G (v)= max{d (v, u): u∈ V} partitions vertices of G into eccentricity layers C k
(G)={v∈ V: e G (v)= rad (G)+ k}, k∈ N, where rad (G)= min{e G (v): v∈ V} is the radius of G.
The paper studies the eccentricity layers of vertices along shortest paths, identifying such …
Abstract
Abstract 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), d (u, x)+ d (v, w) differ by at most 2 δ≥ 0. This paper describes the eccentricity terrain of a δ-hyperbolic graph. The eccentricity function e G (v)= max{d (v, u): u∈ V} partitions vertices of G into eccentricity layers C k (G)={v∈ V: e G (v)= r a d (G)+ k}, k∈ N, where r a d (G)= min{e G (v): v∈ 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. It shows that all sets C≤ k (G)={v∈ V: e G (v)≤ r a d (G)+ k}, k∈ N, are (2 δ− 1)-pseudoconvex. Several bounds on the eccentricity of a vertex are obtained which yield a few approaches to efficiently approximating all eccentricities.
Elsevier
以上显示的是最相近的搜索结果。 查看全部搜索结果