On approximating the number of k-cliques in sublinear time

DOI10.1137/18M1176701MaRDI QIDQ5115700zbMATH OpenOpenAlexFDO

Authors Talya Eden, Dana Ron, 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

zbMATH Keywords

approximation algorithmssublinear algorithmscounting cliques

Mathematics Subject Classification ID

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)

Recommendations

• On approximating the number of k-cliques in sublinear time
• Approximately counting triangles in sublinear time
• Counting stars and other small subgraphs in sublinear-time
• Counting stars and other small subgraphs in sublinear time
• Approximately counting cliques

Cites work

• scientific article; zbMATH DE number 3910446 (Why is no real title available?)
• scientific article; zbMATH DE number 7204459 (Why is no real title available?)
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size
• An Efficient Method for Generating Discrete Random Variables with General Distributions
• An improved constant-time approximation algorithm for maximum~matchings
• Approximately counting triangles in sublinear time
• Approximating Clustering Coefficient and Transitivity
• 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 distance to properties in bounded-degree and general sparse graphs
• Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
• Arboricity and Subgraph Listing Algorithms
• Clique counting in MapReduce: algorithms and experiments
• Computing and Combinatorics
• Counting arbitrary subgraphs in data streams
• Counting stars and other small subgraphs in sublinear-time
• Efficient algorithms for clique problems
• Efficient triangle counting in large graphs via degree-based vertex partitioning
• Estimating the Weight of Metric Minimum Spanning Trees in Sublinear Time
• Experimental and Efficient Algorithms
• If the current clique algorithms are optimal, so is Valiant's parser
• Introduction to Property Testing
• Listing all maximal cliques in large sparse real-world graphs
• Local Graph Partitions for Approximation and Testing
• On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph
• On sampling edges almost uniformly
• On the complexity of fixed parameter clique and dominating set
• Triangle sparsifiers

Cited in

(9)

• Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time
• Approximately counting triangles in sublinear time
• Counting stars and other small subgraphs in sublinear-time
• Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs
• Lower bounds for approximating graph parameters via communication complexity
• 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
• Counting stars and other small subgraphs in sublinear time

Describes a project that uses

Uses Software

• DOULION
• 5tbl

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)