Fast approximation of eccentricities and distances in hyperbolic graphs
From MaRDI portal
Publication:4968378
DOI10.7155/jgaa.00496zbMath1416.05266OpenAlexW2951873711MaRDI QIDQ4968378
Victor Chepoi, H. Alrasheed, Feodor F. Dragan, Yann Vaxès, Michel A. Habib
Publication date: 12 July 2019
Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.7155/jgaa.00496
Related Items
Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs ⋮ Helly-gap of a graph and vertex eccentricities ⋮ Eccentricity terrain of \(\delta\)-hyperbolic graphs ⋮ A story of diameter, radius, and (almost) Helly property ⋮ Eccentricity function in distance-hereditary graphs
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On dynamic shortest paths problems
- Tree 3-spanners on interval, permutation and regular bipartite graphs
- Into the square: on the complexity of some quadratic-time solvable problems
- Sur les groupes hyperboliques d'après Mikhael Gromov. (On the hyperbolic groups à la M. Gromov)
- Almost diameter of a house-hole-free graph in linear time via LexBFS
- LexBFS-orderings and powers of chordal graphs
- The algorithmic use of hypertree structure and maximum neighbourhood orderings
- Finding a central vertex in an HHD-free graph
- Eccentricity-approximating trees in chordal graphs
- Which problems have strongly exponential complexity?
- LexBFS-orderings of distance-hereditary graphs with application to the diametral pair problem
- Fast approximation algorithms for \(p\)-centers in large \(\delta \)-hyperbolic graphs
- Fast approximation of centrality and distances in hyperbolic graphs
- Fast diameter and radius BFS-based computation in (weakly connected) real-world graphs
- Tree-decompositions with bags of small diameter
- Efficient algorithms for center problems in cactus networks
- Eccentricity approximating trees
- Additive spanners and distance and routing labeling schemes for hyperbolic graphs
- On Computing the Gromov Hyperbolicity
- Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters
- 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
- Packing and Covering δ-Hyperbolic Spaces by Balls
- Faster Approximation of Distances in Graphs
- Distance Approximating Trees for Chordal and Dually Chordal Graphs
- Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
- Additive Tree Spanners
- On the power of BFS to determine a graph's diameter
- The absolute center of a network
- New Bounds for Approximating Extremal Distances in Undirected Graphs
- Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
- An Axiomatic and an Average-Case Analysis of Algorithms and Heuristics for Metric Properties of Graphs
- Subquadratic Algorithms for the Diameter and the Sum of Pairwise Distances in Planar Graphs
- Core congestion is inherent in hyperbolic networks
- Metric Embedding, Hyperbolic Space, and Social Networks
- All-Pairs Almost Shortest Paths
- Approximating the Diameter of Planar Graphs in Near Linear Time
- Distance approximating spanning trees
- Fast Approximation and Exact Computation of Negative Curvature Parameters of Graphs
- Collective dynamics of ‘small-world’ networks
- Subcubic Equivalences Between Graph Centrality Problems, APSP and Diameter
- Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
- Better Approximation Algorithms for the Graph Diameter
- Compact oracles for reachability and approximate distances in planar digraphs
- Automata, Languages and Programming
- Fast approximation algorithms for the diameter and radius of sparse graphs
- Network Analysis
- Estimating all pairs shortest paths in restricted graph families: a unified approach
- Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph
- Computing almost shortest paths
- On the complexity of \(k\)-SAT
- Diameter determination on restricted graph families
