Fast approximation of eccentricities and distances in hyperbolic graphs
From MaRDI portal
Recommendations
- Fast approximation of centrality and distances in hyperbolic graphs
- On computing the hyperbolicity of real-world graphs
- Fast approximation algorithms for \(p\)-centers in large \(\delta \)-hyperbolic graphs
- Fast approximation algorithms for \(p\)-centers in large \(\delta\)-hyperbolic graphs
- Fast approximation and exact computation of negative curvature parameters of graphs
Cites work
- scientific article; zbMATH DE number 2084315 (Why is no real title available?)
- scientific article; zbMATH DE number 4031953 (Why is no real title available?)
- scientific article; zbMATH DE number 1385418 (Why is no real title available?)
- scientific article; zbMATH DE number 2119682 (Why is no real title available?)
- scientific article; zbMATH DE number 849252 (Why is no real title available?)
- A simple linear-time algorithm for computing the center of an interval graph
- Additive Tree Spanners
- Additive spanners and distance and routing labeling schemes for hyperbolic graphs
- All-Pairs Almost Shortest Paths
- Almost diameter of a house-hole-free graph in linear time via LexBFS
- An axiomatic and an average-case analysis of algorithms and heuristics for metric properties of graphs
- Approximating the Diameter of Planar Graphs in Near Linear Time
- Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
- Automata, Languages and Programming
- Better approximation algorithms for the graph diameter
- Collective dynamics of `small-world' networks
- Community structure in large networks: natural cluster sizes and the absence of large well-defined clusters
- Compact oracles for reachability and approximate distances in planar digraphs
- Computing almost shortest paths
- Core congestion is inherent in hyperbolic networks
- Diameter determination on restricted graph families
- Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs
- Distance Approximating Trees for Chordal and Dually Chordal Graphs
- Distance approximating spanning trees
- Eccentricity approximating trees
- Eccentricity-approximating trees in chordal graphs
- Efficient algorithms for center problems in cactus networks
- Estimating all pairs shortest paths in restricted graph families: a unified approach
- Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
- Fast approximation algorithms for \(p\)-centers in large \(\delta \)-hyperbolic graphs
- Fast approximation algorithms for the diameter and radius of sparse graphs
- Fast approximation and exact computation of negative curvature parameters of graphs
- Fast approximation of centrality and distances in hyperbolic graphs
- Fast diameter and radius BFS-based computation in (weakly connected) real-world graphs
- Faster Approximation of Distances in Graphs
- Finding a central vertex in an HHD-free graph
- Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
- Into the square: on the complexity of some quadratic-time solvable problems
- LexBFS-orderings and powers of chordal graphs
- LexBFS-orderings of distance-hereditary graphs with application to the diametral pair problem
- Metric embedding, hyperbolic space, and social networks
- Network Analysis
- New bounds for approximating extremal distances in undirected graphs
- On computing the Gromov hyperbolicity
- On computing the hyperbolicity of real-world graphs
- On dynamic shortest paths problems
- On the complexity of k-SAT
- On the power of BFS to determine a graph's diameter
- Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph
- Packing and Covering δ-Hyperbolic Spaces by Balls
- Subcubic equivalences between graph centrality problems, APSP and diameter
- Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs
- Sur les groupes hyperboliques d'après Mikhael Gromov. (On the hyperbolic groups à la M. Gromov)
- The absolute center of a network
- The algorithmic use of hypertree structure and maximum neighbourhood orderings
- Tree 3-spanners on interval, permutation and regular bipartite graphs
- Tree-decompositions with bags of small diameter
- Which problems have strongly exponential complexity?
Cited in
(23)- Additive approximation algorithm for geodesic centers in -hyperbolic graphs
- Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs
- Eccentricity terrain of \(\delta\)-hyperbolic graphs
- Fast approximation algorithms for \(p\)-centers in large \(\delta \)-hyperbolic graphs
- The complexity of diameter on H-free graphs
- Obstructions to faster diameter computation: asteroidal sets
- Easy computation of eccentricity approximating trees
- The complexity of diameter on \(H\)-free graphs
- _i-metric graphs: radius, diameter and all eccentricities
- A story of diameter, radius, and (almost) Helly property
- Eccentricity approximating trees (extended abstract)
- Fast approximation of centrality and distances in hyperbolic graphs
- Algorithms and Computation
- Isometric path complexity of graphs
- Computing the eccentricity distribution of large graphs
- Notes on diameters, centers, and approximating trees of -hyperbolic geodesic spaces and graphs
- Additive spanners and distance and routing labeling schemes for hyperbolic graphs
- Helly-gap of a graph and vertex eccentricities
- Fast approximation algorithms for \(p\)-centers in large \(\delta\)-hyperbolic graphs
- Certificates in P and subquadratic-time computation of radius, diameter, and all eccentricities in graphs
- Eccentricity function in distance-hereditary graphs
- Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs
- $$\alpha _i$$-Metric Graphs: Radius, Diameter and all Eccentricities
This page was built for publication: Fast approximation of eccentricities and distances in hyperbolic graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4968378)
