On computing the diameter of real-world undirected graphs

DOI10.1016/J.TCS.2012.09.018MaRDI QIDQ386904zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

breadth-first searchcomplex networkdiameterexperimental analysis

Mathematics Subject Classification ID

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)

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

Cites work

• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 1875406 (Why is no real title available?)
• All pairs shortest distances for graphs with small integer length edges
• Diameter determination on restricted graph families
• Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs
• Fast computation of empirically tight bounds for the diameter of massive graphs
• Finding the diameter in real-world graphs. Experimentally turning a lower bound into an upper bound
• Kronecker graphs: an approach to modeling networks
• On the all-pairs-shortest-path problem in unweighted undirected graphs.
• Random Geometric Graphs

Cited in

(18)

• On computing the diameter of (weighted) link streams
• Distributed finite-time calculation of node eccentricities, graph radius and graph diameter
• Revisiting decomposition by clique separators
• Succinct enumeration of distant vertex pairs
• Into the square: on the complexity of some quadratic-time solvable problems
• Fast computation of empirically tight bounds for the diameter of massive graphs
• A tie-break model for graph search
• A faster diameter problem algorithm for a chordal graph, with a connection to its center problem
• Fast diameter and radius BFS-based computation in (weakly connected) real-world graphs
• Recognizing graph search trees
• A new application of orthogonal range searching for computing giant graph diameters
• Finding the diameter in real-world graphs. Experimentally turning a lower bound into an upper bound
• Computing giant graph diameters
• Computing the eccentricity distribution of large graphs
• On Computing the Diameter of (Weighted) Link Streams
• The recognition problem of graph search trees
• Algebraic and computer-based methods in the undirected degree/diameter problem - A brief survey
• Eccentricity queries and beyond using hub labels

Describes a project that uses

Uses Software

• Pajek datasets
• SNAP
• MetExplore
• ANF
• Graphs
• UbiCrawler
• KronFit
• WebGraph

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)