A story of diameter, radius, and (almost) Helly property

DOI10.1002/net.21998zbMath1528.05016OpenAlexW3094137245MaRDI QIDQ6087123

Publication date: 11 December 2023

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.21998

zbMATH Keywords

VC-dimension diameter chordal graphs algorithmic graph theory structural graph theory Helly graphs fine-grained complexity in P eccentricity computations

Mathematics Subject Classification ID

Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (1)

Injective hulls of various graph classes

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
A unified approach to recognize squares of split graphs
Into the square: on the complexity of some quadratic-time solvable problems
Covering nearly surface-embedded graphs with a fixed number of balls
Clique graphs and Helly graphs
Algorithms for graphs of bounded treewidth via orthogonal range searching
Covering planar graphs with a fixed number of balls
Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: A note on combinatorial properties of metric spaces
Pseudo-modular graphs
Dismantling absolute retracts of reflexive graphs
A Radon theorem for Helly graphs
Computation of the center and diameter of outerplanar graphs
\(r\)-dominating cliques in graphs with hypertree structure
The algorithmic use of hypertree structure and maximum neighbourhood orderings
Finding a central vertex in an HHD-free graph
Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
Diameter and treewidth in minor-closed graph families
On constructible graphs, infinite bridged graphs and weakly cop-win graphs
Domination in quadrangle-free Helly graphs
A characterisation of rigid circuit graphs
Bounded VC-dimension implies a fractional Helly theorem
Algorithmic graph theory and perfect graphs
Complexity aspects of the Helly property: graphs and hypergraphs
LexBFS-orderings of distance-hereditary graphs with application to the diametral pair problem
An eccentricity 2-approximating spanning tree of a chordal graph is computable in linear time
Fast diameter computation within split graphs
Faster recognition of clique-Helly and hereditary clique-Helly graphs
VC-dimension and Erdős-Pósa property
Six theorems about injective metric spaces
A combinatorial problem; stability and order for models and theories in infinitary languages
On the density of families of sets
The intersection graphs of subtrees in trees are exactly the chordal graphs
A new algorithm for optimal 2-constraint satisfaction and its implications
Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
The Covert Set-Cover Problem with Application to Network Discovery
Identifying Codes in Hereditary Classes of Graphs and VC-Dimension
A simple linear-time algorithm for computing the center of an interval graph
Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs
Packing and Covering δ-Hyperbolic Spaces by Balls
Convexity in Graphs and Hypergraphs
Algorithmic Aspects of Vertex Elimination on Graphs
Dually Chordal Graphs
On constructible graphs, locally Helly graphs, and convexity
On the power of BFS to determine a graph's diameter
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
Diameter computation on H-minor free graphs and graphs of bounded (distance) VC-dimension
Sparse Distance Preservers and Additive Spanners
Fast approximation algorithms for the diameter and radius of sparse graphs
Convexity and fixed-point properties in Helly graphs
Diameter determination on restricted graph families

This page was built for publication: A story of diameter, radius, and (almost) Helly property