Testing graphs in vertex-distribution-free models

DOI10.1145/3313276.3316302zbMath1433.68295OpenAlexW2950524099MaRDI QIDQ5212794

Oded Goldreich

Publication date: 30 January 2020

Published in: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

graph algorithmsproperty testingone-sided vs two-sided error

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

Related Items

Testing graphs against an unknown distribution, Flexible Models for Testing Graph Properties, Local-vs-global combinatorics