Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs
From MaRDI portal
Publication:832869
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
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