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

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

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

Publication date: 25 March 2022

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

Mathematics Subject Classification ID

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

Related Items (3)

Injective hulls of various graph classes ⋮ Helly-gap of a graph and vertex eccentricities ⋮ Distance problems within Helly graphs and \(k\)-Helly graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Hyperbolicity and chordality of a graph
• Into the square: on the complexity of some quadratic-time solvable problems
• Eccentricity function in distance-hereditary graphs
• Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: A note on combinatorial properties of metric spaces
• Dismantling absolute retracts of reflexive graphs
• Computation of the center and diameter of outerplanar graphs
• The algorithmic use of hypertree structure and maximum neighbourhood orderings
• Obstructions to a small hyperbolicity in Helly graphs
• Hyperbolic bridged graphs
• Complexity aspects of the Helly property: graphs and hypergraphs
• LexBFS-orderings of distance-hereditary graphs with application to the diametral pair problem
• Eccentricity terrain of \(\delta\)-hyperbolic graphs
• Computing the Gromov hyperbolicity of a discrete metric space
• Faster recognition of clique-Helly and hereditary clique-Helly graphs
• Six theorems about injective metric spaces
• Recognition of $C_4$-Free and 1/2-Hyperbolic Graphs
• Weakly Modular Graphs and Nonpositive Curvature
• On Computing the Hyperbolicity of Real-World Graphs
• A simple linear-time algorithm for computing the center of an interval graph
• Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs
• Dually Chordal Graphs
• Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
• Subquadratic Algorithms for the Diameter and the Sum of Pairwise Distances in Planar Graphs
• Fast approximation of eccentricities and distances in hyperbolic graphs
• Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs
• Dominating cliques in distance-hereditary graphs
• 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
• Slimness of graphs
• Fast approximation algorithms for the diameter and radius of sparse graphs
• Network Analysis
• On the hyperbolicity of chordal graphs
• Diameter determination on restricted graph families

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