A story of diameter, radius, and (almost) Helly property
From MaRDI portal
Publication:6087123
Recommendations
- Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs
- Distance problems within Helly graphs and \(k\)-Helly graphs
- Helly-gap of a graph and vertex eccentricities
- Diameter, eccentricities and distance oracle computations on H-minor free graphs and graphs of bounded (distance) Vapnik-Chervonenkis dimension
- A faster diameter problem algorithm for a chordal graph, with a connection to its center problem
Cites work
- scientific article; zbMATH DE number 468643 (Why is no real title available?)
- scientific article; zbMATH DE number 554762 (Why is no real title available?)
- scientific article; zbMATH DE number 2119682 (Why is no real title available?)
- A Radon theorem for Helly graphs
- A characterisation of rigid circuit graphs
- A combinatorial problem; stability and order for models and theories in infinitary languages
- A new algorithm for optimal 2-constraint satisfaction and its implications
- A simple linear-time algorithm for computing the center of an interval graph
- A unified approach to recognize squares of split graphs
- Algorithmic Aspects of Vertex Elimination on Graphs
- Algorithmic graph theory and perfect graphs
- Algorithms for graphs of bounded treewidth via orthogonal range searching
- An eccentricity 2-approximating spanning tree of a chordal graph is computable in linear time
- Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
- Bounded VC-dimension implies a fractional Helly theorem
- Clique graphs and Helly graphs
- Complexity aspects of the Helly property: graphs and hypergraphs
- Computation of the center and diameter of outerplanar graphs
- Convexity and fixed-point properties in Helly graphs
- Convexity in Graphs and Hypergraphs
- Covering nearly surface-embedded graphs with a fixed number of balls
- Covering planar graphs with a fixed number of balls
- Diameter and treewidth in minor-closed graph families
- Diameter computation on H-minor free graphs and graphs of bounded (distance) VC-dimension
- Diameter determination on restricted graph families
- Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs
- Dismantling absolute retracts of reflexive graphs
- Domination in quadrangle-free Helly graphs
- Dually Chordal Graphs
- Fast approximation algorithms for the diameter and radius of sparse graphs
- Fast approximation of eccentricities and distances in hyperbolic graphs
- Fast diameter computation within split graphs
- Faster recognition of clique-Helly and hereditary clique-Helly graphs
- Finding a central vertex in an HHD-free graph
- Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
- Graph theory
- Identifying codes in hereditary classes of graphs and VC-dimension
- Into the square: on the complexity of some quadratic-time solvable problems
- Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
- LexBFS-orderings of distance-hereditary graphs with application to the diametral pair problem
- Metric graph theory and geometry: a survey
- On constructible graphs, infinite bridged graphs and weakly cop-win graphs
- On constructible graphs, locally Helly graphs, and convexity
- On the density of families of sets
- On the power of BFS to determine a graph's diameter
- Packing and Covering δ-Hyperbolic Spaces by Balls
- Pseudo-modular graphs
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- Six theorems about injective metric spaces
- Sparse Distance Preservers and Additive Spanners
- Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs
- The algorithmic use of hypertree structure and maximum neighbourhood orderings
- The covert set-cover problem with application to network discovery
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- Tree-structured graphs
- Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: A note on combinatorial properties of metric spaces
- VC-dimension and Erdős-Pósa property
- Voronoi diagrams on planar graphs, and computing the diameter in deterministic \(\tilde{O}(n^{5/3})\) time
- \(r\)-dominating cliques in graphs with hypertree structure
Cited in
(11)- The complexity of diameter on H-free graphs
- Fuzzy median graph and its application in the deployment of wireless sensor networks
- Obstructions to faster diameter computation: asteroidal sets
- Injective hulls of various graph classes
- The complexity of diameter on \(H\)-free graphs
- _i-metric graphs: radius, diameter and all eccentricities
- Parameterized complexity of streaming diameter and connectivity problems
- Certificates in P and subquadratic-time computation of radius, diameter, and all eccentricities in graphs
- Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs
- $$\alpha _i$$-Metric Graphs: Radius, Diameter and all Eccentricities
- Parameterized complexity of streaming diameter and connectivity problems
This page was built for publication: A story of diameter, radius, and (almost) Helly property
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6087123)
