Edge Estimation with Independent Set Oracles

DOI10.1145/3404867MaRDI QIDQ5888944zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

independent set queriesgraph parameter estimation

Mathematics Subject Classification ID

Computer science (68-XX)

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

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)