Edge estimation with independent set oracles
From MaRDI portal
Recommendations
- On triangle estimation using tripartite independent set queries
- On sampling edges almost uniformly
- Approximately counting triangles in sublinear time
- Learning and Verifying Graphs Using Queries with a Focus on Edge Counting
- Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle
Cites work
- Approximately counting triangles in sublinear time
- Approximating average parameters of graphs
- Approximation and Online Algorithms
- Comparing the strength of query types in property testing: the case of \(k\)-colorability
- Concentration of Measure for the Analysis of Randomized Algorithms
- Counting stars and other small subgraphs in sublinear-time
- On Approximating the Depth and Related Problems
- On Approximation Algorithms for # P
- On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph
- Shortest paths in intersection graphs of unit disks
Cited in
(11)- Learning and Verifying Graphs Using Queries with a Focus on Edge Counting
- Optimal identification of sets of edges using 2-factors
- Parameterized query complexity of hitting set using stability of sunflowers
- Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle
- On sampling edges almost uniformly
- Edge Estimation with Independent Set Oracles
- Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems
- Constructing large matchings via query access to a maximal matching oracle
- On coarse and fine approximate counting of t-cliques
- Faster counting and sampling algorithms using colorful decision oracle
- On triangle estimation using tripartite independent set queries
This page was built for publication: Edge estimation with independent set oracles
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4993304)
