Mathematical Research Data Initiative
Main page
Recent changes
Random page
SPARQL
MaRDI@GitHub
New item
Special pages
In other projects
MaRDI portal item
Discussion
View source
View history
English
Log in

Edge Estimation with Independent Set Oracles

From MaRDI portal
Publication:5888944
Jump to:navigation, search

DOI10.1145/3404867OpenAlexW3087345281MaRDI QIDQ5888944FDOQ5888944


Authors: Cyrus Rashtchian, Makrand Sinha, Paul Beame, Sariel Har-Peled Edit this on Wikidata


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)

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:5888944&oldid=30759698"
Tools
What links here
Related changes
Printable version
Permanent link
Page information
This page was last edited on 7 March 2024, at 06:06. Warning: Page may not contain recent updates.
Privacy policy
About MaRDI portal
Disclaimers
Imprint
Powered by MediaWiki