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

graph parameter estimationindependent set queries

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

(10)

• Optimal identification of sets of edges using 2-factors
• Almost optimal query algorithm for hitting set using a subset query
• Nearly optimal independence oracle algorithms for edge estimation in hypergraphs
• How packed is it, really?
• Faster counting and sampling algorithms using colorful decision oracle
• Learning-augmented query policies for minimum spanning tree with uncertainty
• Non-adaptive edge counting and sampling via bipartite independent set queries
• Learning spanning forests optimally in weighted undirected graphs with CUT queries
• Cut-query algorithms with few rounds
• Algorithms that access the input via 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 Q5888944)