Back to Search
Start Over
Eccentricity terrain of δ-hyperbolic graphs.
- Source :
-
Journal of Computer & System Sciences . Sep2020, Vol. 112, p50-65. 16p. - Publication Year :
- 2020
-
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. [ABSTRACT FROM AUTHOR]
- Subjects :
- *APPROXIMATION algorithms
Subjects
Details
- Language :
- English
- ISSN :
- 00220000
- Volume :
- 112
- Database :
- Academic Search Index
- Journal :
- Journal of Computer & System Sciences
- Publication Type :
- Academic Journal
- Accession number :
- 143102234
- Full Text :
- https://doi.org/10.1016/j.jcss.2020.03.004