Counting Stars and Other Small Subgraphs in Sublinear-Time

DOI10.1137/100783066zbMath1234.68138OpenAlexW1994987445MaRDI QIDQ3225127

Dana Ron, Mira Gonen, Yuval Shavitt

Publication date: 15 March 2012

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/100783066

zbMATH Keywords

approximate countingsubgraphssublinear-time algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (17)

On triangle estimation using tripartite independent set queries ⋮ Motif estimation via subgraph sampling: the fourth-moment phenomenon ⋮ Bootstrapping exchangeable random graphs ⋮ Sublinear-time algorithms for monomer-dimer systems on bounded degree graphs ⋮ Unnamed Item ⋮ Subsampling spectral clustering for stochastic block models in large-scale networks ⋮ Approximately Counting Triangles in Sublinear Time ⋮ Seeding with Costly Network Information ⋮ On a Conjecture of Feige for Discrete Log-Concave Distributions ⋮ On Approximating the Number of $k$-Cliques in Sublinear Time ⋮ Unnamed Item ⋮ Sublinear-time algorithms for counting star subgraphs via edge sampling ⋮ Bootstrap estimators for the tail-index and for the count statistics of graphex processes ⋮ Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems ⋮ Unnamed Item ⋮ Sublinear Time Estimation of Degree Distribution Moments: The Arboricity Connection ⋮ Quantum Chebyshev's Inequality and Applications

This page was built for publication: Counting Stars and Other Small Subgraphs in Sublinear-Time