Sublinear-time algorithms for counting star subgraphs via edge sampling
From MaRDI portal
Publication:1709591
DOI10.1007/s00453-017-0287-3zbMath1391.68120arXiv1601.04233OpenAlexW2586277680MaRDI QIDQ1709591
Maryam Aliakbarpour, John Peebles, Ronitt Rubinfeld, Themis Gouleakis, Anak Yodpinyanee, Amartya Shankha Biswas
Publication date: 6 April 2018
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1601.04233
Analysis of algorithms and problem complexity (68Q25) Database theory (68P15) Graph theory (including graph drawing) in computer science (68R10) Enumeration in graph theory (05C30) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)
Related Items
Motif estimation via subgraph sampling: the fourth-moment phenomenon, Estimating the number of connected components in a graph via subgraph sampling, Unnamed Item, Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems, Unnamed Item, Sublinear Time Estimation of Degree Distribution Moments: The Arboricity Connection, A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Faster algorithms for finding and counting subgraphs
- Finding and counting given length cycles
- Property testing lower bounds via communication complexity
- Tracking join and self-join sizes in limited storage
- Motifs in evolving cooperative networks look like protein structure networks
- Finding paths of length \(k\) in \(O^{*}(2^k)\) time
- Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
- A sublinear-time approximation scheme for bin packing
- The space complexity of approximating the frequency moments
- Selectivity and cost estimation for joins based on random sampling
- Finding, Minimizing, and Counting Weighted Subgraphs
- Approximate Counting of Cycles in Streams
- Improved Constant-Time Approximation Algorithms for Maximum Matchings and Other Optimization Problems
- Counting Arbitrary Subgraphs in Data Streams
- Counting Stars and Other Small Subgraphs in Sublinear-Time
- Approximating average parameters of graphs
- Optimal approximations of the frequency moments of data streams
- Simpler algorithm for estimating frequency moments of data streams
- Balanced Hashing, Color Coding and Approximate Counting
- Approximately Counting Triangles in Sublinear Time
- The Parameterized Complexity of Counting Problems
- A Fast Approximation Algorithm for Computing the Frequencies of Subgraphs in a Given Graph
- Discovering and Exploiting Statistical Properties for Query Optimization in Relational Databases: A Survey
- On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing
- Testing Probability Distributions Underlying Aggregated Data
- Local Graph Partitions for Approximation and Testing
- Approximating the Number of Network Motifs
- Estimating Sum by Weighted Sampling
- On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph
- Research in Computational Molecular Biology
- Efficient Triangle Counting in Large Graphs via Degree-Based Vertex Partitioning
- Counting Subgraphs via Homomorphisms
