Approximating average parameters of graphs
DOI10.1002/RSA.20203zbMATH Open1155.05057OpenAlexW3090803701MaRDI QIDQ3514701FDOQ3514701
Authors: Oded Goldreich, Dana Ron 
Publication date: 21 July 2008
Published in: Random Structures \& Algorithms (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2006/553/
Recommendations
- Approximating Average Parameters of Graphs
- Approximating the statistics of various properties in randomly weighted graphs
- On average eccentricity of graphs
- Average distance in graphs and eigenvalues
- The average Laplacian polynomial of a graph
- Approximating the average stretch factor of geometric graphs
- Approximating the average stretch factor of geometric graphs
- An averaging process on hypergraphs
- An approximability-related parameter on graphs -- properties and applications
Wiener indexrandomized approximation algorithmssublinear-time algorithmsdistance queriesaverage distance in a grapheverage degree of a graphstandard neighbor queries
Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Vertex degrees (05C07) Distance in graphs (05C12)
Cites Work
Cited In (37)
- On triangle estimation using tripartite independent set queries
- Sublinear-time algorithms for monomer-dimer systems on bounded degree graphs
- On ultrametric 1-median selection
- Sublinear-time Algorithms
- Average distance queries through weighted samples in graphs and metric spaces: high scalability with tight statistical guarantees
- Deterministic metric 1-median selection with A \(1-o(1)\) fraction of points ignored
- Spreading messages
- Approximately counting triangles in sublinear time
- Deterministic metric 1-median selection with very few queries
- Motif estimation via subgraph sampling: the fourth-moment phenomenon
- Edge estimation with independent set oracles
- On sampling edges almost uniformly
- A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size
- Quantum Chebyshev's Inequality and Applications
- Introduction to testing graph properties
- The arboricity captures the complexity of sampling edges
- Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter
- Introduction to testing graph properties
- Bootstrap estimators for the tail-index and for the count statistics of graphex processes
- Sublinear time estimation of degree distribution moments: the arboricity connection
- A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling
- Lower bounds for approximating graph parameters via communication complexity
- On the Complexity of Sampling Vertices Uniformly from a Graph
- A lower bound for metric 1-median selection
- Some results on approximate 1-median selection in metric spaces
- An averaging process on hypergraphs
- Sublinear time approximation of the cost of a metric \(k\)-nearest neighbor graph
- Comparing the strength of query types in property testing: the case of \(k\)-colorability
- Approximating Average Parameters of Graphs
- On approximating the number of \(k\)-cliques in sublinear time
- Estimating the number of connected components in a graph via subgraph sampling
- Title not available (Why is that?)
- On sums of independent random variables with unbounded variance, and estimating the average degree in a graph
- Almost optimal query algorithm for hitting set using a subset query
- Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems
- Sublinear-time algorithms for counting star subgraphs via edge sampling
- On Las Vegas approximations for metric 1-median selection
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 Q3514701)
