Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs

DOI10.1145/1377676.1377687zbMATH Open1221.68295OpenAlexW1965650021MaRDI QIDQ3602902FDOQ3602902

Authors: Victor Chepoi, Feodor F. Dragan, Bertrand Estellon, Yann Vaxès, M. 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

Mathematics Subject Classification ID

Trees (05C05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Cited In (49)

• A review of two network curvature measures
• Fast approximation and exact computation of negative curvature parameters of graphs
• Eccentricity terrain of \(\delta\)-hyperbolic graphs
• Why did the shape of your network change? (On detecting network anomalies via non-local curvatures)
• Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs
• Topologically trivial closed walks in directed surface graphs
• Easy computation of eccentricity approximating trees
• An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs
• Algebraic characterisation of relatively hyperbolic special groups
• \( \alpha_i\)-metric graphs: radius, diameter and all eccentricities
• Notes on diameters, centers, and approximating trees of δ-hyperbolic geodesic spaces and graphs
• A story of diameter, radius, and (almost) Helly property
• Obstructions to a small hyperbolicity in Helly graphs
• Coning-off CAT(0) cube complexes
• Connected tree-width
• On the complexity of computing treebreadth
• Leanness computation: small values and special graph classes
• Data center interconnection networks are not hyperbolic
• Parameterized approximation algorithms for some location problems in graphs
• On the hyperbolicity of random graphs
• Into the square: on the complexity of some quadratic-time solvable problems
• On the hyperbolicity of bipartite graphs and intersection graphs
• To Approximate Treewidth, Use Treelength!
• On the joint spectral radius for isometries of non-positively curved spaces and uniform growth
• Applying clique-decomposition for computing Gromov hyperbolicity
• How to use spanning trees to navigate in graphs
• Constant approximation algorithms for embedding graph metrics into trees and outerplanar graphs
• On the Complexity of Computing Treebreadth
• First-order logic axiomatization of metric graph theory
• On computing discretized Ricci curvatures of graphs: local algorithms and (localized) fine-grained reductions
• Fast approximation of eccentricities and distances in hyperbolic graphs
• Differential geometric treewidth estimation in adiabatic quantum computation
• Weakly Modular Graphs and Nonpositive Curvature
• Helly-gap of a graph and vertex eccentricities
• Fast approximation algorithms for \(p\)-centers in large \(\delta\)-hyperbolic graphs
• Metric embedding, hyperbolic space, and social networks
• Title not available (Why is that?)
• Beyond Helly graphs: the diameter problem on absolute retracts
• Helly groups
• Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs
• \(k\)-chordal graphs: from cops and robber to compact routing via treewidth
• $$\alpha _i$$-Metric Graphs: Radius, Diameter and all Eccentricities
• A counterexample to Thiagarajan's conjecture on regular event structures
• Tree decompositions and social graphs
• Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic $\tilde{O}(n^{5/3})$ Time
• Fellow travelers phenomenon present in real-world networks
• Fast Approximation and Exact Computation of Negative Curvature Parameters of Graphs
• Effect of Gromov-hyperbolicity parameter on cuts and expansions in graphs and some algorithmic implications
• On computing the diameter of real-world undirected graphs

This page was built for publication: Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3602902)