A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling
From MaRDI portal
Recommendations
Cites work
- scientific article; zbMATH DE number 6862103 (Why is no real title available?)
- scientific article; zbMATH DE number 2119719 (Why is no real title available?)
- scientific article; zbMATH DE number 7204459 (Why is no real title available?)
- A hybrid sampling scheme for triangle counting
- A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size
- A second look at counting triangles in graph streams (corrected)
- An improved constant-time approximation algorithm for maximum~matchings
- Approximating average parameters of graphs
- Approximating the Minimum Spanning Tree Weight in Sublinear Time
- Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time
- Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
- Computing and Combinatorics
- Counting arbitrary subgraphs in data streams
- Counting stars and other small subgraphs in sublinear time
- Estimating the weight of metric minimum spanning trees in sublinear-time
- How hard is counting triangles in the streaming model?
- Introduction to Property Testing
- Local Graph Partitions for Approximation and Testing
- Lower bounds for approximating graph parameters via communication complexity
- On approximating the number of k-cliques in sublinear time
- On sampling edges almost uniformly
- On sums of independent random variables with unbounded variance, and estimating the average degree in a graph
- On the number of copies of one hypergraph in another
- On the number of subgraphs of prescribed type of graphs with a given number of edges
- Sublinear-time algorithms for counting star subgraphs via edge sampling
- Tight Bounds for Testing Bipartiteness in General Graphs
- Worst-case optimal join algorithms
Cited in
(11)- Counting simplices in hypergraph streams
- Brief announcement: improved massively parallel triangle counting in O(1) rounds
- Better sum estimation via weighted sampling
- Erasure-resilient sublinear-time graph algorithms
- Quantum Chebyshev's Inequality and Applications
- Towards optimal dynamic indexes for approximate (and exact) triangle counting
- The arboricity captures the complexity of sampling edges
- Sampling arbitrary subgraphs exactly uniformly in sublinear time
- Efficient and Near-optimal Algorithms for Sampling Small Connected Subgraphs
- Join and subgraph sampling under degree constraints
- Sublinear-time algorithms for counting star subgraphs via edge sampling
This page was built for publication: A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5090376)
