Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs

DOI10.1007/978-3-030-83508-8_22OpenAlexW3198400301MaRDI QIDQ832869FDOQ832869

Authors: Feodor F. Dragan, Guillaume Ducoffe, Heather M. Guarnera 

Publication date: 25 March 2022

Full work available at URL: https://arxiv.org/abs/2102.08349

Mathematics Subject Classification ID

Data structures (68P05) Algorithms in computer science (68Wxx)

Cites Work

• Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: A note on combinatorial properties of metric spaces
• Title not available (Why is that?)
• Six theorems about injective metric spaces
• Fast approximation algorithms for the diameter and radius of sparse graphs
• Network Analysis
• Diameter determination on restricted graph families
• The algorithmic use of hypertree structure and maximum neighbourhood orderings
• Hyperbolic bridged graphs
• Dually Chordal Graphs
• Hyperbolicity and chordality of a graph
• On the hyperbolicity of chordal graphs
• Title not available (Why is that?)
• Dominating cliques in distance-hereditary graphs
• Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs
• Complexity aspects of the Helly property: graphs and hypergraphs
• Recognition of \(C_4\)-free and \(1/2\)-hyperbolic graphs
• On computing the hyperbolicity of real-world graphs
• Computing the Gromov hyperbolicity of a discrete metric space
• Dismantling absolute retracts of reflexive graphs
• Faster recognition of clique-Helly and hereditary clique-Helly graphs
• Slimness of graphs
• Metric graph theory and geometry: a survey
• A simple linear-time algorithm for computing the center of an interval graph
• Computation of the center and diameter of outerplanar graphs
• LexBFS-orderings of distance-hereditary graphs with application to the diametral pair problem
• Into the square: on the complexity of some quadratic-time solvable problems
• Eccentricity terrain of \(\delta\)-hyperbolic graphs
• Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
• Fast approximation of eccentricities and distances in hyperbolic graphs
• Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
• Eccentricity function in distance-hereditary graphs
• Obstructions to a small hyperbolicity in Helly graphs
• Weakly Modular Graphs and Nonpositive Curvature
• Title not available (Why is that?)
• Voronoi diagrams on planar graphs, and computing the diameter in deterministic \(\tilde{O}(n^{5/3})\) time
• Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs
• Multivariate analysis of orthogonal range searching and graph distances
• Fast approximation and exact computation of negative curvature parameters of graphs
• Diameter computation on H-minor free graphs and graphs of bounded (distance) VC-dimension

Cited In (6)

• Injective hulls of various graph classes
• \( \alpha_i\)-metric graphs: radius, diameter and all eccentricities
• Helly-gap of a graph and vertex eccentricities
• Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs
• Distance problems within Helly graphs and \(k\)-Helly graphs
• $$\alpha _i$$-Metric Graphs: Radius, Diameter and all Eccentricities

This page was built for publication: Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs

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