scientific article; zbMATH DE number 7204459

DOI10.4230/LIPICS.ICALP.2017.7MaRDI QIDQ5111336zbMATH OpenFDO

Authors Talya Eden, Dana Ron, C. Seshadhri

Publication date 27 May 2020

zbMATH Keywords

degree distributionsublinear algorithmsgraph moments

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Analysis of algorithms (68W40) Vertex degrees (05C07)

Recommendations

• Sublinear time estimation of degree distribution moments: the arboricity connection
• Counting stars and other small subgraphs in sublinear time
• Counting stars and other small subgraphs in sublinear-time
• On sums of independent random variables with unbounded variance, and estimating the average degree in a graph
• Approximately counting triangles in sublinear time

Cited in

(8)

• Quantum Chebyshev's Inequality and Applications
• The arboricity captures the complexity of sampling edges
• 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
• Efficient estimation algorithms for neighborhood variance and other moments
• On approximating the number of \(k\)-cliques in sublinear time
• On sums of independent random variables with unbounded variance, and estimating the average degree in a graph

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111336)