On triangle estimation using tripartite independent set queries
DOI10.1007/S00224-021-10043-YOpenAlexW3166345458MaRDI QIDQ825973FDOQ825973
Authors: Anup Bhattacharya, Arijit Bishnu, Arijit Ghosh, Gopinath Mishra 
Publication date: 18 December 2021
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1808.00691
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Enumeration in graph theory (05C30)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- A hybrid sampling scheme for triangle counting
- A second look at counting triangles in graph streams (corrected)
- Approximately counting and sampling small witnesses using a colourful decision oracle
- Approximately counting triangles in sublinear time
- Approximating average parameters of graphs
- Computing and Combinatorics
- Computing exact minimum cuts without knowing the graph
- Concentration of measure for the analysis of randomized algorithms.
- Counting arbitrary subgraphs in data streams
- Counting stars and other small subgraphs in sublinear-time
- Edge estimation with independent set oracles
- Finding a Minimum Circuit in a Graph
- Finding and counting given length cycles
- Fine-grained reductions from approximate counting to decision
- Large deviations for sums of partly dependent random variables
- Listing triangles
- On Approximation Algorithms for # P
- On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph
- On approximating the number of k-cliques in sublinear time
- Optimal query complexity bounds for finding graphs
- The power of an example: hidden set size approximation using group queries and conditional sampling
Cited In (6)
- Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle
- Edge Estimation with Independent Set Oracles
- Approximately counting triangles in sublinear time
- Motif estimation via subgraph sampling: the fourth-moment phenomenon
- Edge estimation with independent set oracles
- Almost optimal query algorithm for hitting set using a subset query
This page was built for publication: On triangle estimation using tripartite independent set queries
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q825973)
