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

DOI10.1016/J.TCS.2015.02.033MaRDI QIDQ2347002zbMATH OpenOpenAlexFDO

Authors Michele Borassi, Pilu Crescenzi, Andrea Marino, Frank W. Takes, M. 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

actors graphgraph diametergraph radiusWikipedia graph

Mathematics Subject Classification ID

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

Recommendations

• On computing the diameter of real-world undirected graphs
• On the power of BFS to determine a graph's diameter
• Fast and Simple Approximation of the Diameter and Radius of a Graph
• Fast approximation algorithms for the diameter and radius of sparse graphs
• scientific article; zbMATH DE number 2086230
• Fast computation of empirically tight bounds for the diameter of massive graphs
• Fast diameter computation within split graphs
• Fast diameter computation within split graphs

Cites work

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

Cited in

(12)

• Eccentricity queries and beyond using hub labels
• A note on the complexity of computing the number of reachable vertices in a digraph
• A faster diameter problem algorithm for a chordal graph, with a connection to its center problem
• Finding the diameter in real-world graphs. Experimentally turning a lower bound into an upper bound
• On computing the diameter of real-world undirected graphs
• Fast approximation of eccentricities and distances in hyperbolic graphs
• Toward Tight Approximation Bounds for Graph Diameter and Eccentricities
• Approximation algorithms for min-distance problems
• Parameterized complexity of diameter
• Computation of diameter, radius and center of permutation graphs
• Certificates in P and subquadratic-time computation of radius, diameter, and all eccentricities in graphs
• Approximation algorithms for min-distance problems in DAGs

Describes a project that uses

Uses Software

• KONECT
• DBpedia
• SNAP

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2347002)