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

• 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?
• Triangle counting in dynamic graph streams

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)

Cites Work

• On Approximation Algorithms for # P
• Listing Triangles
• Finding and counting given length cycles
• Finding a Minimum Circuit in a Graph
• Title not available (Why is that?)
• Large deviations for sums of partly dependent random variables
• A second look at counting triangles in graph streams (corrected)
• Counting arbitrary subgraphs in data streams
• Computing and Combinatorics
• Approximating average parameters of graphs
• Title not available (Why is that?)
• Counting stars and other small subgraphs in sublinear-time
• On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph
• Concentration of measure for the analysis of randomized algorithms.
• Optimal query complexity bounds for finding graphs
• A Hybrid Sampling Scheme for Triangle Counting
• Approximately Counting Triangles in Sublinear Time
• The Power of an Example
• Title not available (Why is that?)
• Title not available (Why is that?)
• Approximately counting and sampling small witnesses using a colourful decision oracle
• Fine-grained reductions from approximate counting to decision
• On approximating the number of k-cliques in sublinear time

Cited In (3)

• Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle
• Motif estimation via subgraph sampling: the fourth-moment phenomenon
• 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)