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

(14)

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

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)