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

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2017.7

zbMATH Keywords

degree distributiongraph momentssublinear algorithms

Mathematics Subject Classification ID

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

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

(11)

• 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
• Lower bounds for approximating graph parameters via communication complexity
• A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling
• The arboricity captures the complexity of sampling edges
• Quantum Chebyshev's Inequality and Applications
• On approximating the number of k-cliques in sublinear time
• Efficient estimation algorithms for neighborhood variance and other moments
• Improved sublinear-time moment estimation using weighted sampling
• Better sum estimation via weighted sampling
• Erasure-resilient sublinear-time graph algorithms

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)