On Approximating the Number of $k$-Cliques in Sublinear Time
From MaRDI portal
Publication:5115700
DOI10.1137/18M1176701zbMath1452.68276OpenAlexW3043603630MaRDI QIDQ5115700
Dana Ron, Talya Eden, C. Seshadhri
Publication date: 18 August 2020
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/18m1176701
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25) Randomized algorithms (68W20)
Related Items
Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs, Efficient and Near-optimal Algorithms for Sampling Small Connected Subgraphs, Unnamed Item
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the complexity of fixed parameter clique and dominating set
- Efficient algorithms for clique problems
- Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
- Clique Counting in MapReduce
- Triangle Sparsifiers
- Counting Arbitrary Subgraphs in Data Streams
- Counting Stars and Other Small Subgraphs in Sublinear-Time
- Approximating Clustering Coefficient and Transitivity
- Approximating average parameters of graphs
- An Efficient Method for Generating Discrete Random Variables with General Distributions
- Estimating the Weight of Metric Minimum Spanning Trees in Sublinear Time
- Arboricity and Subgraph Listing Algorithms
- If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser
- Approximately Counting Triangles in Sublinear Time
- Approximating the distance to properties in bounded-degree and general sparse graphs
- Local Graph Partitions for Approximation and Testing
- An improved constant-time approximation algorithm for maximum~matchings
- On Sampling Edges Almost Uniformly
- Listing All Maximal Cliques in Large Sparse Real-World Graphs
- Approximating the Minimum Spanning Tree Weight in Sublinear Time
- Introduction to Property Testing
- On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph
- Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time
- Experimental and Efficient Algorithms
- Computing and Combinatorics
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
- Efficient Triangle Counting in Large Graphs via Degree-Based Vertex Partitioning
