Approximating Average Parameters of Graphs

DOI10.1007/11830924_34zbMATH Open1155.68571OpenAlexW1593323337MaRDI QIDQ3595407FDOQ3595407

Authors: Oded Goldreich, Dana Ron 

Publication date: 28 August 2007

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2006/553/

Recommendations

• Approximating average parameters of graphs
• Sublinear-time algorithms for approximating graph parameters
• Distance Approximation in Bounded-Degree and General Sparse Graphs
• Counting stars and other small subgraphs in sublinear time
• Counting stars and other small subgraphs in sublinear-time

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Approximation algorithms (68W25)

Cited In (11)

• Average distance queries through weighted samples in graphs and metric spaces: high scalability with tight statistical guarantees
• Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
• Separating sublinear time computations by approximate diameter
• Separating Sublinear Time Computations by Approximate Diameter
• Approximating average parameters of graphs
• Sublinear graph augmentation for fast query implementation
• A sublinear-time approximation scheme for bin packing
• Erasure-resilient sublinear-time graph algorithms
• Sublinear time estimation of degree distribution moments: the arboricity connection
• An averaging process on hypergraphs
• On sums of independent random variables with unbounded variance, and estimating the average degree in a graph

This page was built for publication: Approximating Average Parameters of Graphs

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