On computing the diameter of real-world undirected graphs
DOI10.1016/J.TCS.2012.09.018zbMATH Open1278.68230OpenAlexW2044124066MaRDI QIDQ386904FDOQ386904
Authors: Roberto Grossi, Leonardo Lanzi, Andrea Marino, Pilu Crescenzi, Michel Habib 
Publication date: 11 December 2013
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2012.09.018
Recommendations
- Computing giant graph diameters
- Fast diameter and radius BFS-based computation in (weakly connected) real-world graphs
- Finding the diameter in real-world graphs. Experimentally turning a lower bound into an upper bound
- Fast and Simple Approximation of the Diameter and Radius of a Graph
- Fast computation of empirically tight bounds for the diameter of massive graphs
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Network design and communication in computer systems (68M10)
Cites Work
- Kronecker graphs: an approach to modeling networks
- Random Geometric Graphs
- Title not available (Why is that?)
- Diameter determination on restricted graph families
- On the all-pairs-shortest-path problem in unweighted undirected graphs.
- Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs
- Fast computation of empirically tight bounds for the diameter of massive graphs
- All pairs shortest distances for graphs with small integer length edges
- Finding the diameter in real-world graphs. Experimentally turning a lower bound into an upper bound
- Title not available (Why is that?)
Cited In (18)
- On computing the diameter of (weighted) link streams
- Finding the diameter in real-world graphs. Experimentally turning a lower bound into an upper bound
- Distributed finite-time calculation of node eccentricities, graph radius and graph diameter
- A new application of orthogonal range searching for computing giant graph diameters
- The recognition problem of graph search trees
- Revisiting decomposition by clique separators
- Into the square: on the complexity of some quadratic-time solvable problems
- Fast computation of empirically tight bounds for the diameter of massive graphs
- Recognizing graph search trees
- A faster diameter problem algorithm for a chordal graph, with a connection to its center problem
- Computing the eccentricity distribution of large graphs
- A tie-break model for graph search
- Eccentricity queries and beyond using hub labels
- Computing giant graph diameters
- Fast diameter and radius BFS-based computation in (weakly connected) real-world graphs
- Algebraic and computer-based methods in the undirected degree/diameter problem - A brief survey
- Succinct enumeration of distant vertex pairs
- On Computing the Diameter of (Weighted) Link Streams
Uses Software
This page was built for publication: On computing the diameter of real-world undirected graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q386904)
