Fast diameter and radius BFS-based computation in (weakly connected) real-world graphs

DOI10.1016/j.tcs.2015.02.033zbMath1328.05179OpenAlexW127322189MaRDI QIDQ2347002

Pierluigi Crescenzi, Frank W. Takes, Michele Borassi, Andrea Marino, Michel A. Habib, Walter A. Kosters

Publication date: 26 May 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2015.02.033

zbMATH Keywords

graph diametergraph radiusactors graphWikipedia graph

Mathematics Subject Classification ID

Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Related Items (8)

A note on the complexity of computing the number of reachable vertices in a digraph ⋮ Eccentricity queries and beyond using hub labels ⋮ A faster diameter problem algorithm for a chordal graph, with a connection to its center problem ⋮ Computation of diameter, radius and center of permutation graphs ⋮ Unnamed Item ⋮ Fast approximation of eccentricities and distances in hyperbolic graphs ⋮ Parameterized complexity of diameter ⋮ Toward Tight Approximation Bounds for Graph Diameter and Eccentricities

Uses Software

• SNAP
• KONECT
• DBpedia

Cites Work

• Unnamed Item
• Unnamed Item
• On computing the diameter of real-world undirected graphs
• Which problems have strongly exponential complexity?
• Computing the eccentricity distribution of large graphs
• Is the Boston subway a small-world network?
• Analysis and enumeration. Algorithms for biological graphs
• Efficient algorithms for center problems in cactus networks
• Network analysis. Methodological foundations.
• Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
• The Structure and Function of Complex Networks
• On the power of BFS to determine a graph's diameter
• Better Approximation Algorithms for the Graph Diameter
• Fast computation of empirically tight bounds for the diameter of massive graphs
• Multiplying matrices faster than coppersmith-winograd
• Fast approximation algorithms for the diameter and radius of sparse graphs
• Digraphs
• Diameter determination on restricted graph families

This page was built for publication: Fast diameter and radius BFS-based computation in (weakly connected) real-world graphs