Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs
From MaRDI portal
Publication:3602902
DOI10.1145/1377676.1377687zbMath1221.68295OpenAlexW1965650021MaRDI QIDQ3602902
Victor Chepoi, Bertrand Estellon, Yann Vaxès, Feodor F. Dragan, Michel A. Habib
Publication date: 12 February 2009
Published in: Proceedings of the twenty-fourth annual symposium on Computational geometry (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1377676.1377687
Trees (05C05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)
Related Items (44)
Obstructions to a small hyperbolicity in Helly graphs ⋮ Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs ⋮ Data center interconnection networks are not hyperbolic ⋮ How to use spanning trees to navigate in graphs ⋮ On the hyperbolicity of bipartite graphs and intersection graphs ⋮ Notes on diameters, centers, and approximating trees of δ-hyperbolic geodesic spaces and graphs ⋮ Differential geometric treewidth estimation in adiabatic quantum computation ⋮ Metric embedding, hyperbolic space, and social networks ⋮ Applying clique-decomposition for computing Gromov hyperbolicity ⋮ Helly-gap of a graph and vertex eccentricities ⋮ Fast approximation and exact computation of negative curvature parameters of graphs ⋮ On computing the diameter of real-world undirected graphs ⋮ Why did the shape of your network change? (On detecting network anomalies via non-local curvatures) ⋮ Beyond Helly graphs: the diameter problem on absolute retracts ⋮ Eccentricity terrain of \(\delta\)-hyperbolic graphs ⋮ A counterexample to Thiagarajan's conjecture on regular event structures ⋮ On the hyperbolicity of random graphs ⋮ On computing discretized Ricci curvatures of graphs: local algorithms and (localized) fine-grained reductions ⋮ A story of diameter, radius, and (almost) Helly property ⋮ First-order logic axiomatization of metric graph theory ⋮ Effect of Gromov-hyperbolicity parameter on cuts and expansions in graphs and some algorithmic implications ⋮ An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs ⋮ Topologically trivial closed walks in directed surface graphs ⋮ Constant approximation algorithms for embedding graph metrics into trees and outerplanar graphs ⋮ \(k\)-chordal graphs: from cops and robber to compact routing via treewidth ⋮ A review of two network curvature measures ⋮ Easy computation of eccentricity approximating trees ⋮ On the complexity of computing treebreadth ⋮ To Approximate Treewidth, Use Treelength! ⋮ Algebraic characterisation of relatively hyperbolic special groups ⋮ Unnamed Item ⋮ Parameterized approximation algorithms for some location problems in graphs ⋮ Connected tree-width ⋮ On the joint spectral radius for isometries of non-positively curved spaces and uniform growth ⋮ Fast approximation algorithms for \(p\)-centers in large \(\delta\)-hyperbolic graphs ⋮ Into the square: on the complexity of some quadratic-time solvable problems ⋮ Weakly Modular Graphs and Nonpositive Curvature ⋮ Fast approximation of eccentricities and distances in hyperbolic graphs ⋮ On the Complexity of Computing Treebreadth ⋮ Fast Approximation and Exact Computation of Negative Curvature Parameters of Graphs ⋮ Fellow travelers phenomenon present in real-world networks ⋮ Tree decompositions and social graphs ⋮ Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic $\tilde{O}(n^{5/3})$ Time ⋮ Coning-off CAT(0) cube complexes
This page was built for publication: Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs
