Fast and Simple Approximation of the Diameter and Radius of a Graph

DOI10.1007/11764298_9MaRDI QIDQ5307536zbMATH OpenOpenAlexFDO

Authors Krists Boitmanis, Karlis Freivalds, Pēteris Lediņš, Rūdolfs Opmanis

Publication date 14 September 2007

Published in Experimental Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11764298_9

zbMATH Keywords

analysis of algorithmsgraph algorithmsgraph diameteralgorithm engineeringapproximation techniques

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Approximation algorithms (68W25)

Recommendations

• Fast approximation algorithms for the diameter and radius of sparse graphs
• Linear-time graph distance and diameter approximation
• Approximating the Diameter of Planar Graphs in Near Linear Time
• Approximating the diameter of planar graphs in near linear time
• Faster Approximation of Distances in Graphs
• Better approximation algorithms for the graph diameter
• Fast diameter computation within split graphs
• Fast diameter computation within split graphs
• On approximating the \(d\)-girth of a graph
• On Approximating the d-Girth of a Graph

Cited in

(11)

• Fast approximation algorithms for the diameter and radius of sparse graphs
• Fast approximation of betweenness centrality through sampling
• Improved outerplanarity bounds for planar graphs
• On Trade-Offs in External-Memory Diameter-Approximation
• Fast computation of empirically tight bounds for the diameter of massive graphs
• Fast diameter computation within split graphs
• Computing giant graph diameters
• Fast diameter and radius BFS-based computation in (weakly connected) real-world graphs
• Faster Approximation of Distances in Graphs
• On computing the diameter of real-world undirected graphs
• I/O-efficient hierarchical diameter approximation

This page was built for publication: Fast and Simple Approximation of the Diameter and Radius of a Graph

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