Edge Estimation with Independent Set Oracles

DOI10.1145/3404867OpenAlexW3087345281MaRDI QIDQ5888944FDOQ5888944

Authors: Cyrus Rashtchian, Makrand Sinha, Paul Beame, Sariel Har-Peled 

Publication date: 26 April 2023

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3404867

Recommendations

• Edge estimation with independent set oracles
• 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

zbMATH Keywords

independent set queriesgraph parameter estimation

Mathematics Subject Classification ID

Computer science (68-XX)

Cited In (3)

• Algorithms that access the input via queries
• Optimal identification of sets of edges using 2-factors
• Almost optimal query algorithm for hitting set using a subset query

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 Q5888944)