On triangle estimation using tripartite independent set queries
DOI10.1007/s00224-021-10043-yOpenAlexW3166345458MaRDI QIDQ825973
Arijit Bishnu, Anup Bhattacharya, 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
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Enumeration in graph theory (05C30) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)
Related Items (3)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Finding and counting given length cycles
- Optimal query complexity bounds for finding graphs
- A second look at counting triangles in graph streams (corrected)
- Counting Arbitrary Subgraphs in Data Streams
- Counting Stars and Other Small Subgraphs in Sublinear-Time
- Approximating average parameters of graphs
- On Approximation Algorithms for # P
- Finding a Minimum Circuit in a Graph
- A Hybrid Sampling Scheme for Triangle Counting
- Approximately Counting Triangles in Sublinear Time
- Large deviations for sums of partly dependent random variables
- The Power of an Example
- Approximately counting and sampling small witnesses using a colourful decision oracle
- Listing Triangles
- Fine-grained reductions from approximate counting to decision
- On approximating the number of k-cliques in sublinear time
- On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph
- Computing and Combinatorics
- Concentration of Measure for the Analysis of Randomized Algorithms
This page was built for publication: On triangle estimation using tripartite independent set queries
