Approximating Average Parameters of Graphs

DOI10.1007/11830924_34MaRDI QIDQ3595407zbMATH OpenOpenAlexFDO

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/

Mathematics Subject Classification ID

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

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

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)