Approximating average parameters of graphs

DOI10.1002/rsa.20203zbMath1155.05057OpenAlexW3090803701MaRDI QIDQ3514701

Oded Goldreich, Dana Ron

Publication date: 21 July 2008

Published in: Random Structures and Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

Wiener indexrandomized approximation algorithmssublinear-time algorithmsdistance queriesaverage distance in a grapheverage degree of a graphstandard neighbor queries

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Vertex degrees (05C07)

Related Items

On triangle estimation using tripartite independent set queries ⋮ Motif estimation via subgraph sampling: the fourth-moment phenomenon ⋮ On Sampling Edges Almost Uniformly ⋮ A lower bound for metric 1-median selection ⋮ Estimating the number of connected components in a graph via subgraph sampling ⋮ On ultrametric 1-median selection ⋮ Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter ⋮ Sublinear-time algorithms for monomer-dimer systems on bounded degree graphs ⋮ Unnamed Item ⋮ Approximately Counting Triangles in Sublinear Time ⋮ Almost optimal query algorithm for hitting set using a subset query ⋮ Some results on approximate 1-median selection in metric spaces ⋮ On Approximating the Number of $k$-Cliques in Sublinear Time ⋮ Comparing the strength of query types in property testing: the case of \(k\)-colorability ⋮ Unnamed Item ⋮ Deterministic metric 1-median selection with A \(1-o(1)\) fraction of points ignored ⋮ Sublinear-time algorithms for counting star subgraphs via edge sampling ⋮ Introduction to Testing Graph Properties ⋮ Bootstrap estimators for the tail-index and for the count statistics of graphex processes ⋮ On the Complexity of Sampling Vertices Uniformly from a Graph ⋮ On Las Vegas approximations for metric 1-median selection ⋮ Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems ⋮ Sublinear-time Algorithms ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Sublinear Time Estimation of Degree Distribution Moments: The Arboricity Connection ⋮ Introduction to Testing Graph Properties ⋮ A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling ⋮ Quantum Chebyshev's Inequality and Applications ⋮ Spreading messages ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Sublinear time algorithms for metric space problems
• Automata, Languages and Programming
• Computing almost shortest paths