On triangle estimation using tripartite independent set queries

DOI10.1007/S00224-021-10043-YMaRDI QIDQ825973zbMATH OpenOpenAlexFDO

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, https://drops.dagstuhl.de/opus/volltexte/2019/11515/

zbMATH Keywords

query complexitysublinear algorithmtriangle estimation

Mathematics Subject Classification ID

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)

Recommendations

• Approximately counting triangles in sublinear time
• Edge estimation with independent set oracles
• A hybrid sampling scheme for triangle counting
• How hard is counting triangles in the streaming model?

Cites work

• scientific article; zbMATH DE number 2119719 (Why is no real title available?)
• scientific article; zbMATH DE number 7561379 (Why is no real title available?)
• 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)

• Edge estimation with independent set oracles
• Approximately counting triangles in sublinear time
• Edge Estimation with Independent Set Oracles
• Almost optimal query algorithm for hitting set using a subset query
• Motif estimation via subgraph sampling: the fourth-moment phenomenon
• Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle

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)