On computing the diameter of real-world undirected graphs

DOI10.1016/J.TCS.2012.09.018zbMath1278.68230OpenAlexW2044124066MaRDI QIDQ386904

Leonardo Lanzi, Andrea Marino, Roberto Grossi, Pierluigi Crescenzi, Michel A. 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

diameterexperimental analysiscomplex networkbreadth-first search

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (9)

Recognizing graph search trees ⋮ Eccentricity queries and beyond using hub labels ⋮ A faster diameter problem algorithm for a chordal graph, with a connection to its center problem ⋮ A tie-break model for graph search ⋮ Revisiting Decomposition by Clique Separators ⋮ Computing the eccentricity distribution of large graphs ⋮ Into the square: on the complexity of some quadratic-time solvable problems ⋮ The Recognition Problem of Graph Search Trees ⋮ Fast diameter and radius BFS-based computation in (weakly connected) real-world graphs

Uses Software

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the all-pairs-shortest-path problem in unweighted undirected graphs.
• All pairs shortest distances for graphs with small integer length edges
• Finding the Diameter in Real-World Graphs
• Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs
• Random Geometric Graphs
• Fast computation of empirically tight bounds for the diameter of massive graphs
• Diameter determination on restricted graph families

This page was built for publication: On computing the diameter of real-world undirected graphs