A comparison of three algorithms for approximating the distance distribution in real-world graphs

DOI10.1007/978-3-642-19754-3_11MaRDI QIDQ2999337zbMATH OpenOpenAlexFDO

Authors Pilu Crescenzi, Roberto Grossi, Leonardo Lanzi, Andrea Marino

Publication date 12 May 2011

Published in Theory and Practice of Algorithms in (Computer) Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-19754-3_11

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Distance in graphs (05C12)

Recommendations

• Faster Approximation of Distances in Graphs
• Robust distance queries on massive networks
• Efficient distributed computation of distance sketches in networks
• Fast Approximation of Centrality
• Fast approximation algorithms for the diameter and radius of sparse graphs

Cited in

(3)

• Average distance queries through weighted samples in graphs and metric spaces: high scalability with tight statistical guarantees
• Computing the eccentricity distribution of large graphs
• Information theory perspective on network robustness

Describes a project that uses

Uses Software

• ANF

This page was built for publication: A comparison of three algorithms for approximating the distance distribution in real-world graphs

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