Fast computation of empirically tight bounds for the diameter of massive graphs

DOI10.1145/1412228.1455266zbMath1284.05300arXiv0904.2728OpenAlexW2034050320MaRDI QIDQ5406179

Matthieu Latapy, Clémence Magnien, Michel A. Habib

Publication date: 1 April 2014

Published in: ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0904.2728

zbMATH Keywords

graph diameterdiameter bounds

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (10)

On the hyperbolicity of bipartite graphs and intersection graphs ⋮ Seeking community structure in networks via biogeography-based optimization with consensus dynamics ⋮ On computing the diameter of real-world undirected graphs ⋮ On Trade-Offs in External-Memory Diameter-Approximation ⋮ Approximation of the Diagonal of a Laplacian’s Pseudoinverse for Complex Network Analysis ⋮ Computing the eccentricity distribution of large graphs ⋮ Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems ⋮ On Computing the Gromov Hyperbolicity ⋮ Via Detours to I/O-Efficient Shortest Paths ⋮ Fast diameter and radius BFS-based computation in (weakly connected) real-world graphs

This page was built for publication: Fast computation of empirically tight bounds for the diameter of massive graphs