On approximating the number of k-cliques in sublinear time
DOI10.1137/18M1176701zbMATH Open1452.68276OpenAlexW3043603630MaRDI QIDQ5115700FDOQ5115700
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
Recommendations
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Cites Work
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
- Title not available (Why is that?)
- Arboricity and Subgraph Listing Algorithms
- Triangle sparsifiers
- Counting Arbitrary Subgraphs in Data Streams
- Computing and Combinatorics
- Efficient triangle counting in large graphs via degree-based vertex partitioning
- Approximating average parameters of graphs
- Counting Stars and Other Small Subgraphs in Sublinear-Time
- An improved constant-time approximation algorithm for maximum~matchings
- Approximating the Minimum Spanning Tree Weight in Sublinear Time
- On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph
- Title not available (Why is that?)
- Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
- Approximating Clustering Coefficient and Transitivity
- An Efficient Method for Generating Discrete Random Variables with General Distributions
- On the complexity of fixed parameter clique and dominating set
- Local Graph Partitions for Approximation and Testing
- Approximating the distance to properties in bounded-degree and general sparse graphs
- Introduction to Property Testing
- Experimental and Efficient Algorithms
- Approximately Counting Triangles in Sublinear Time
- If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser
- Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time
- Listing All Maximal Cliques in Large Sparse Real-World Graphs
- Efficient algorithms for clique problems
- Estimating the Weight of Metric Minimum Spanning Trees in Sublinear Time
- Clique counting in MapReduce: algorithms and experiments
- On Sampling Edges Almost Uniformly
- Title not available (Why is that?)
Cited In (6)
- Title not available (Why is that?)
- Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs
- Approximation Algorithms for the k-Clique Covering Problem
- Efficient and Near-optimal Algorithms for Sampling Small Connected Subgraphs
- On approximating the number of k-cliques in sublinear time
- Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time
Uses Software
This page was built for publication: On approximating the number of \(k\)-cliques in sublinear time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5115700)
