Approximating average parameters of graphs

Wiener index randomized approximation algorithms sublinear-time algorithms distance queries average distance in a graph everage degree of a graph standard neighbor queries

Mathematics Subject Classification ID

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

Cites Work

Sublinear time algorithms for metric space problems
Title not available (Why is that?)
Automata, Languages and Programming
Computing almost shortest paths (extended abstract)

Cited In (34)

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
Title not available (Why is that?)
Sublinear Time Estimation of Degree Distribution Moments: The Arboricity Connection
Deterministic metric 1-median selection with A $1-o(1)$ fraction of points ignored
Spreading messages
Title not available (Why is that?)
Deterministic metric 1-median selection with very few queries
Motif estimation via subgraph sampling: the fourth-moment phenomenon
On Approximating the Number of $k$-Cliques in Sublinear Time
Quantum Chebyshev's Inequality and Applications
Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter
Bootstrap estimators for the tail-index and for the count statistics of graphex processes
A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling
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
Approximately Counting Triangles in Sublinear Time
Introduction to Testing Graph Properties
Introduction to Testing Graph Properties
Estimating the number of connected components in a graph via subgraph sampling
Title not available (Why is that?)
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
Title not available (Why is that?)
On Sampling Edges Almost Uniformly
Title not available (Why is that?)

   Recommendations

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)