A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling
From MaRDI portal
Publication:5090376
DOI10.4230/LIPIcs.ITCS.2019.6OpenAlexW2962774460MaRDI QIDQ5090376
Sanjeev Khanna, Sepehr Assadi, Michael Kapralov
Publication date: 18 July 2022
Full work available at URL: https://arxiv.org/abs/1811.07780
Related Items (3)
Efficient and Near-optimal Algorithms for Sampling Small Connected Subgraphs ⋮ Unnamed Item ⋮ Quantum Chebyshev's Inequality and Applications
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
- On the number of subgraphs of prescribed type of graphs with a given number of edges
- On the number of copies of one hypergraph in another
- Sublinear-time algorithms for counting star subgraphs via edge sampling
- A second look at counting triangles in graph streams (corrected)
- Counting Arbitrary Subgraphs in Data Streams
- Approximating average parameters of graphs
- On sums of independent random variables with unbounded variance, and estimating the average degree in a graph
- Estimating the weight of metric minimum spanning trees in sublinear-time
- Worst-case Optimal Join Algorithms
- A Hybrid Sampling Scheme for Triangle Counting
- Tight Bounds for Testing Bipartiteness in General Graphs
- Local Graph Partitions for Approximation and Testing
- An improved constant-time approximation algorithm for maximum~matchings
- On approximating the number of k-cliques in sublinear time
- On Sampling Edges Almost Uniformly
- Approximating the Minimum Spanning Tree Weight in Sublinear Time
- How Hard Is Counting Triangles in the Streaming Model?
- Introduction to Property Testing
- Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time
- Computing and Combinatorics
This page was built for publication: A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling
